// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 20, P = 1e9 + 7;

int n, F[N][N][N][N][N][N], G[N][N][N][N][N][N];

// (1, 3, 2) - (2, 1, 3) - (3, 2, 1)

char s[N * 3];

void inline add(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}

void inline cp() {
	for (int a = 0; a <= n; a++) 
		for (int b = 0; b + a <= n; b++) 
			for (int c = 0; c + b + a <= n; c++) 
				for (int d = 0; d + c + b + a <= n; d++) 
					for (int e = 0; e + d + c + b + a <= n; e++) 
						for (int f = 0; f + e + d + c + b + a <= n; f++) {
							G[a][b][c][d][e][f] = F[a][b][c][d][e][f];
							F[a][b][c][d][e][f] = 0;
						}
}

int main() {
	int T; read(T);
    while (T--) {
    	memset(F, 0, sizeof F);
    	read(n); scanf("%s", s + 1);

    	F[0][0][0][0][0][0] = 1;
    	for (int i = 1; i <= 3 * n; i++) {
    		cp();
    		for (int a = 0; a <= n; a++) {
    			for (int b = 0; b + a <= n; b++) {
    				for (int c = 0; c + b + a <= n; c++) {
    					for (int d = 0; d + c + b + a <= n; d++) {
    						for (int e = 0; e + d + c + b + a <= n; e++) {
    							for (int f = 0; f + e + d + c + b + a <= n; f++) {
    								if (!G[a][b][c][d][e][f]) continue;
    								int w = G[a][b][c][d][e][f], t = f + e + d + c + b + a;
    								if (s[i] == '0' || s[i] == '1') {
    									if (t < n) add(F[a + 1][b][c][d][e][f], w);
    									if (c) add(F[a][b][c - 1][d + 1][e][f], 1ll * w * c % P);
    									if (f) add(F[a][b][c][d][e][f - 1], 1ll * w * f % P);
    								}
    								if (s[i] == '0' || s[i] == '2') {
    									if (t < n) add(F[a][b][c + 1][d][e][f], w);
    									if (b) add(F[a][b - 1][c][d][e][f], 1ll * w * b % P);
    									if (e) add(F[a][b][c][d][e - 1][f + 1], 1ll * w * e % P);
    								}
    								if (s[i] == '0' || s[i] == '3') {
    									if (t < n) add(F[a][b][c][d][e + 1][f], w);
    									if (a) add(F[a - 1][b + 1][c][d][e][f], 1ll * w * a % P);
    									if (d) add(F[a][b][c][d - 1][e][f], 1ll * w * d % P);
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    	int o = F[0][0][0][0][0][0];
    	for (int i = 2; i <= n; i++) o = 1ll * o * i % P;
    	printf("%d\n", o);
    }
    return 0;
}