#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
using namespace std;
inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())
		if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
int T,n,f[2][21][21][21][21][21][21],cur,m,p; char ch[60];
void init(int x){ m=((__int128)1<<64)/x,p=x; }
void Mod(int &x){ x=x-(__int128(x)*m>>64)*p; }
inline void sol(const int &x){
	for (int i=0;i<=n;i++)
	for (int j=0;i+j<=n;j++)
	for (int k=0;i+j+k<=n;k++)
	for (int a=0;i+j+k+a<=n;a++)
	for (int b=0;i+j+k+a+b<=n;b++)
	for (int c=0;i+j+k+a+b+c<=n;c++)
		switch (x){
			case 1:{
				f[cur][i][j][k][a][b][c]+=
				(i ? f[cur^1][i-1][j][k][a][b][c]:0)+
				(a ? f[cur^1][i][j+1][k][a-1][b][c]*(j+1):0)+
				f[cur^1][i][j][k][a][b][c+1]*(c+1);
				break;
			}
			case 2:{
				f[cur][i][j][k][a][b][c]+=
				(j ? f[cur^1][i][j-1][k][a][b][c]:0)+
				(c ? f[cur^1][i][j][k+1][a][b][c-1]*(k+1):0)+
				f[cur^1][i][j][k][a][b+1][c]*(b+1);
				break;
			}
			case 3:{
				f[cur][i][j][k][a][b][c]+=
				(k ? f[cur^1][i][j][k-1][a][b][c]:0)+
				(b ? f[cur^1][i+1][j][k][a][b-1][c]*(i+1):0)+
				f[cur^1][i][j][k][a+1][b][c]*(a+1);
				break;
			}
		}
}
inline void modf(){
	for (int i=0;i<=n;i++)
	for (int j=0;i+j<=n;j++)
	for (int k=0;i+j+k<=n;k++)
	for (int a=0;i+j+k+a<=n;a++)
	for (int b=0;i+j+k+a+b<=n;b++)
	for (int c=0;i+j+k+a+b+c<=n;c++)
		Mod(f[cur][i][j][k][a][b][c]);
}
inline void clear(){
	for (int i=0;i<=n+1;i++)
	for (int j=0;i+j<=n+1;j++)
	for (int k=0;i+j+k<=n+1;k++)
	for (int a=0;i+j+k+a<=n+1;a++)
	for (int b=0;i+j+k+a+b<=n+1;b++)
	for (int c=0;i+j+k+a+b+c<=n+1;c++)
		f[cur][i][j][k][a][b][c]=0;
}
signed main(){
	init(mod);
	for (T=read();T--;){
		n=read(),scanf("%s",ch+1);
		cur=0,clear();
		f[cur][0][0][0][0][0][0]=1;
		int fnc=1;
		for (int i=1;i<=3*n;i++){
			if (i<=n) fnc=fnc*i%mod;
			cur^=1,clear();
			if (ch[i]=='1'||ch[i]=='0') sol(1);
			if (ch[i]=='2'||ch[i]=='0') sol(2);
			if (ch[i]=='3'||ch[i]=='0') sol(3);
			if (i%3==0) modf();
		}
		printf("%lld\n",f[cur][0][0][0][0][0][0]*fnc%mod);
	}
	return 0;
}