#include<bits/stdc++.h>
using namespace std;
#define loop(i) for(int j=0;j<=min(i,n);j++) for(int k=0;k<=min(i,n)&&j+k<=n;k++) for(int l=0;l<=min(i,n)&&j+k+l<=n;l++) for(int r=0;r<=min(i,n)&&j+k+l+r<=n;r++) for(int p=0;p<=min(i,n)&&j+k+l+r+p<=n;p++) for(int q=0;q<=min(i,n)&&j+k+l+r+p+q<=n;q++)
int t,n;
long long ans,f[21][21][21][21][21][21],g[21][21][21][21][21][21];
char s[61];
const int mod=1e9+7;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%s",&n,s+1);
		loop(n) g[j][k][l][r][p][q]=0;
		g[0][0][0][0][0][0]=1;
		for(int i=1;i<=n*3;i++){
			loop(i){
				swap(f[j][k][l][r][p][q],g[j][k][l][r][p][q]);
				g[j][k][l][r][p][q]=0;
			}
			loop(i){
				long long v=f[j][k][l][r][p][q];
				if(s[i]=='0'||s[i]=='1'){
					(g[j+1][k][l][r][p][q]+=v)%=mod;
					if(k) (g[j][k-1][l][r][p+1][q]+=v*k)%=mod;
					if(q) (g[j][k][l][r][p][q-1]+=v*q)%=mod;
				}
				if(s[i]=='0'||s[i]=='2'){
					(g[j][k+1][l][r][p][q]+=v)%=mod;
					if(l) (g[j][k][l-1][r][p][q+1]+=v*l)%=mod;
					if(r) (g[j][k][l][r-1][p][q]+=v*r)%=mod;
				}
				if(s[i]=='0'||s[i]=='3'){
					(g[j][k][l+1][r][p][q]+=v)%=mod;
					if(j) (g[j-1][k][l][r+1][p][q]+=v*j)%=mod;
					if(p) (g[j][k][l][r][p-1][q]+=v*p)%=mod;
				}
			}
		}
		ans=g[0][0][0][0][0][0];
		for(int i=1;i<=n;i++) (ans*=i)%=mod;
		printf("%lld\n",ans);
	}
	return 0;
}