#include<bits/stdc++.h>
using namespace std;
int mian(); int main() { return mian(); }
/*
给定常为 $3n$，值域为 $[0,3]$ 的序列 $S$，可以将其中的 $0$ 更改为 $[1,3]$ 得到 $T$ 
求出对所有 $T$，合法的 $a$ 的数量的和 
合法的 $a$ 表示为长为 $n$ 的三元序列 ${a_{i,1},a_{i,2},a_{i,3}}$ ，满足 
$(T_{a_{i,1}},T_{a_{i,2}},T_{a_{i,3}})=(1,3,2)\space or\space (2,1,3)\space or\space (3,2,1)$
且 $a_{i,1}<a_{i,2}<a_{i,3}$ ，每个 $a$ 互不相同 
$n\le 19, mod = 10^9+7$
$1s,1G$

因为只有三种形态，那么每一次新加入的一个字符，就是要让这个字符与之前的某个未完成的前缀 $a$ 进行匹配，或者继续成为一个未完成的前缀 
因为空间很大，直接设计 `f[i][j][k][o][p][q]`，表示到当前位置（状态中省略，滚动），已经有 $(i,j,k,o,p,q)$ 个未完成匹配的前缀是 $(1, 2, 3, 13, 21, 32)$
每一次直接根据这一位是什么转移即可，时间复杂度 $O(3*n^7)$，因为还要枚举当前位置，但是因为状态和只有 $n$，因此存在巨大的常数 
答案即为没有任何前缀没有匹配，即全为 $0$ 
注意题目中的 $a$ 之间是互相没有限制，即每一个匹配完成的 $a$ 可以在任何顺序，因此要加上一个阶乘 
同理，转移过程中的每一步都要在所有的方案中选择一个数字转移，因此每一步都要乘上选走的东西的方案数（就是与这个数拼接的所有前缀都可以选且是不同的，因此每种方案都要计算） 
注意只需要乘上选择某一个数的方案而不需要乘上放入的方案，因为放入时是无序的，所以取出时才需要选择 
*/
#define ll long long
const int N = 20;
const int mod = 1e9 + 7;
int n, S;

int f[2][N][N][N][N][N][N];

#define FOR \
	for(int i = 0; i <= n; ++i) \
		for(int j = 0; j + i <= n; ++j) \
			for(int k = 0; i + j + k <= n; ++k) \
				for(int o = 0; i + j + k + o <= n; ++o) \
					for(int p = 0; i + j + k + o + p <= n; ++p) \
						for(int q = 0; i + j + k + o + p + q <= n; ++q) 
//多一个1，多一个21，多一个完成匹配 
void doo1(const int now)  {
	FOR f[now][i][j][k][o][p][q] = ( ( i ? (ll)f[now ^ 1][i - 1][j][k][o][p][q] : 0 ) + ( p and j < n ? (ll)f[now ^ 1][i][j + 1][k][o][p - 1][q] * (j + 1) % mod : 0 ) + ( q < n ? (ll)f[now ^ 1][i][j][k][o][p][q + 1] * (q + 1) % mod : 0 ) ) % mod;
}
void doo2(const int now) {
	FOR f[now][i][j][k][o][p][q] = ( ( j ? (ll)f[now ^ 1][i][j - 1][k][o][p][q] : 0 ) + ( q and k < n ? (ll)f[now ^ 1][i][j][k + 1][o][p][q - 1] * (k + 1) % mod : 0 ) + ( o < n ? (ll)f[now ^ 1][i][j][k][o + 1][p][q] * (o + 1) % mod : 0 ) ) % mod;
}
void doo3(const int now) {
	FOR f[now][i][j][k][o][p][q] = ( ( k ? (ll)f[now ^ 1][i][j][k - 1][o][p][q] : 0 ) + ( o and i < n ? (ll)f[now ^ 1][i + 1][j][k][o - 1][p][q] * (i + 1) % mod : 0 ) + ( p < n ? (ll)f[now ^ 1][i][j][k][o][p + 1][q] * (p + 1) % mod : 0 ) ) % mod;
}
void doo0(const int now) {
	FOR f[now][i][j][k][o][p][q] = ( ( i ? (ll)f[now ^ 1][i - 1][j][k][o][p][q] : 0 ) + ( p and j < n ? (ll)f[now ^ 1][i][j + 1][k][o][p - 1][q] * (j + 1) % mod : 0 ) + ( q < n ? (ll)f[now ^ 1][i][j][k][o][p][q + 1] * (q + 1) % mod : 0 ) + 
									 ( j ? (ll)f[now ^ 1][i][j - 1][k][o][p][q] : 0 ) + ( q and k < n ? (ll)f[now ^ 1][i][j][k + 1][o][p][q - 1] * (k + 1) % mod : 0 ) + ( o < n ? (ll)f[now ^ 1][i][j][k][o + 1][p][q] * (o + 1) % mod : 0 ) + 
									 ( k ? (ll)f[now ^ 1][i][j][k - 1][o][p][q] : 0 ) + ( o and i < n ? (ll)f[now ^ 1][i + 1][j][k][o - 1][p][q] * (i + 1) % mod : 0 ) + ( p < n ? (ll)f[now ^ 1][i][j][k][o][p + 1][q] * (p + 1) % mod : 0 ) ) % mod;
}
void out(const int now, const int it) {
	FOR if(f[now][i][j][k][o][p][q]) printf("%d f[%d][%d][%d][%d][%d][%d]=%d\n", it, i, j, k, o, p, q, f[now][i][j][k][o][p][q]);
}

void solve() {
	scanf("%d", &n);
	
	memset(f, 0, sizeof f);
	f[1][0][0][0][0][0][0] = 1;
	int now = 0;
	int fac = 1;
	
	for(int i = 1; i <= 3 * n; ++i) {
		scanf("%1d", &S);
		if( i <= n ) fac = (ll)fac * i % mod;
		switch(S) {
			case 1 : { doo1(now); break; }
			case 2 : { doo2(now); break; }
			case 3 : { doo3(now); break; }
			default: { doo0(now); }
		}
		now ^= 1;
	}
	printf("%lld\n", (ll)fac * f[now ^ 1][0][0][0][0][0][0] % mod);
}
int mian() {
	int T; scanf("%d", &T);
	while(T--) solve();
	return 0;
} /*
1
19
202000300003001300011000011021320001000300320020302022103
*/