#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20,mod=1e9+7;
int n,f[2][N][N][N][N][N][N];
char ch[N*3];
void sol(){
	for(int a=0;a<=n;a++){
		for(int b=0;a+b<=n;b++){
			for(int c=0;a+b+c<=n;c++){
				for(int d=0;a+b+c+d<=n;d++){
					for(int e=0;a+b+c+d+e<=n;e++){
						for(int g=0;a+b+c+d+e+g<=n;g++){
							f[0][a][b][c][d][e][g]=0;
							f[1][a][b][c][d][e][g]=0;
						}
					}
				}
			}
		}
	}
	scanf("%lld%s",&n,ch+1);
	f[0][0][0][0][0][0][0]=1;
	for(int I=1;I<=n*3;I++){
		int i=I&1,j=i^1;
//		memset(f[i],0,sizeof(f[i]));
		for(int a=0;a<=n;a++){
			for(int b=0;a+b<=n;b++){
				for(int c=0;a+b+c<=n;c++){
					for(int d=0;a+b+c+d<=n;d++){
						for(int e=0;a+b+c+d+e<=n;e++){
							for(int g=0;a+b+c+d+e+g<=n;g++){
								int &x=f[i][a][b][c][d][e][g];x=0;
								if(ch[I]=='1'||ch[I]=='0'){
									x=(x+((a>0)?f[j][a-1][b][c][d][e][g]:0)+((e>0&&b<n)?f[j][a][b+1][c][d][e-1][g]*(b+1)%mod:0)+((g<n)?f[j][a][b][c][d][e][g+1]*(g+1)%mod:0));
								}
								if(ch[I]=='2'||ch[I]=='0'){
									x=(x+((b>0)?f[j][a][b-1][c][d][e][g]:0)+((g>0&&c<n)?f[j][a][b][c+1][d][e][g-1]*(c+1)%mod:0)+((d<n)?f[j][a][b][c][d+1][e][g]*(d+1)%mod:0));
								}
								if(ch[I]=='3'||ch[I]=='0'){
									x=(x+((c>0)?f[j][a][b][c-1][d][e][g]:0)+((d>0&&a<n)?f[j][a+1][b][c][d-1][e][g]*(a+1)%mod:0)+((e<n)?f[j][a][b][c][d][e+1][g]*(e+1)%mod:0));
								}
								x%=mod;
							}
						}
					}
				}
			}
		}
	}
	int ans=f[(n*3)&1][0][0][0][0][0][0];
	for(int i=1;i<=n;i++)ans=ans*i%mod;
	printf("%lld\n",ans);
}
signed main(){
	int t;cin>>t;
	while(t--)sol();
	return 0;
}