#include<bits/stdc++.h>
#pragma GCC optimize(3) 
using namespace std;
typedef long long ll;
typedef double db;
#define re register
#define inf 1e9+10
#define mod 998244353
#define lim 1<<18
#define max(a,b) a>=b?a:b
#define min(a,b) a<=b?a:b
//#define int ll
int n;
ll k[lim][20],q[lim],d[lim];
int m[20][20],t[lim],p[lim];
int read()
{
	int x = 0;
	char c, f = 1;
	while (!isdigit(c = getchar()) && c != '-');
	if (c == '-')c = getchar(), f = -1;
	do x = x * 10 + (c ^ '0');
	while (isdigit(c = getchar()));
	return x * f;
}
signed main(){
		ios_base::sync_with_stdio(false);cin.tie(0);
	n=read();
	for(int i=1;i< (1<<n);i++) t[i]=i&(-i);
	for(int i=1;i<=n;i++){
		for(int j=0;j<n;j++) p[j]=read();
		int	kk=0;
		while(p[kk]!=i) kk+=1;
		for(int j=0;j<kk;j++) 
		m[p[j]][i]=1;
	} 
	for(int i=1;i<=n;i++){
		k[1 << (i - 1)][i]=1;
		q[1 << (i - 1)]=1;
	}
	for(int x=1;x<1<<n;x++){
		for(int i=1;i<=n;i++){
			if(!k[x][i]) continue;
			for(int j=1;j<=n;j++){
				if(!m[i][j])continue;
				if(t[x] >1 << (j-1)) continue;
				if(x&(1<<(j-1))){
					if(t[x]==((1 << (j - 1))))q[x]+=k[x][i];
				}
				else k[x | (1 << (j - 1))][j] += k[x][i]; 
			}
		}
	}
	q[0]=1;
	d[0]=1;
	for(int x=1;x<(1<<n);x++){
		int j=x-t[x];
		while(1){
			d[x] += q[x ^ j] * d[j];
      		  if (!j) break;
        	j = x - t[x] & j - 1	;		
		}
	} 
	int Q;
	Q=read();
	while(Q--){
		int l=0,r=0;
		char s[20];
		scanf("%s",s);
		for(int i=0;i<n;i++){
			if(s[i]=='H') l |= 1 << i;
			else r |= 1 << i;
		}
		printf("%lld\n",d[l] * d[r]);
	} 
	return 0;
}

数据过弱，这个卡常算法考场单个点1800+ms，luogu上最高500+ms

@ chen_zhe