#include<iostream>
#include<cstring>
#include<vector>
#include<chrono>
#include<stdint.h>
#include<unordered_map>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;

vector<int> pos[19 * 3 + 1];
LL q[657800];
int p[657800][7];
int l[8];
LL pow20[8];
int g[8][4];
int dp[657800];

template<typename Key, typename Val, const unsigned int M = 1 << 20, const Val DefaultValue = Val()>
struct HashTable{
    static constexpr uint32_t shift = 64 - __lg(M);
    const uint64_t r;

    static constexpr uint64_t rng() {
        uint64_t x = chrono::steady_clock::now().time_since_epoch().count();
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

	int tim[M];
    Val val[M];
	Key keys[M];
	int h[M], ne[M], idx;
	int cur;

	HashTable() : r(rng()), cur(1) {}

	void clear(){
		idx = 0;
		++cur;
	}

    bool contains(const Key &key){
        uint32_t k = key * r >> shift;
		if (tim[k] != cur) return false;
		for(int i = h[k]; ~i; i = ne[i])
			if (keys[i] == key) return true;
		return false;
    }

    int insert(const Key &key){
        uint32_t k = key * r >> shift;
		if (tim[k] != cur){
			tim[k] = cur;
			h[k] = -1;
		}
		for(int i = h[k]; ~i; i = ne[i])
			if (keys[i] == key) return i;
        keys[idx] = key, ne[idx] = h[k], val[idx] = DefaultValue, h[k] = idx++;
		return idx - 1;
    }
    
    Val &operator[](const Key &key){
        return val[insert(key)];
    }
    
    void erase(const Key &key){
        tim[insert(key)] = -1;
    }
    
};

HashTable<LL, int> mp;


int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    // 132
    // 213
    // 321
    pow20[0] = 1;
    for(int i = 1; i < 8; i++) pow20[i] = pow20[i - 1] * 20;

    l[0] = 0;
    l[1] = l[2] = l[3] = 1;
    l[4] = l[5] = l[6] = 2;
    l[7] = 3;
    memset(g, -1, sizeof g);
    g[0][1] = 1;
    g[1][3] = 4;
    g[4][2] = 7;
    g[0][2] = 2;
    g[2][1] = 5;
    g[5][3] = 7;
    g[0][3] = 3;
    g[3][2] = 6;
    g[6][1] = 7;

    int T;
    cin >> T;
    while(T--){
        int n; string s;
        cin >> n >> s;
        for(int i = 0; i <= 3 * n; i++) pos[i].clear();

        mp.clear();

        int c[7]{}; int tot = 0;
        auto dfs = [&](auto &&dfs, int u, int len, int cnt, LL val) -> void {
            if (u == 7){
                len += (n - cnt) * 3;
                pos[len].push_back(tot);
                memcpy(p[tot], c, sizeof c);
                mp[val] = tot;
                q[tot] = val;
                dp[tot] = 0;
                tot += 1;
                return;
            }
            for(int i = 0; cnt + i <= n; i++){
                c[u] = i;
                dfs(dfs, u + 1, len + l[u] * i, cnt + i, val + pow20[u] * i);
            }
        };

        dfs(dfs, 0, 0, 0, 0);

        dp[pos[0][0]] = 1;

        for(int i = 0; i < 3 * n; i++){
            int l = 1, r = 3;
            if (s[i] != '0') l = r = s[i] - '0';
            for(auto x : pos[i]){
                for(int j = 0; j < 7; j++){
                    if (p[x][j] != 0){
                        for(int k = l; k <= r; k++){
                            if (g[j][k] != -1){
                                LL nval = q[x] - pow20[j];
                                if (g[j][k] != 7) nval += pow20[g[j][k]];
                                int nxt = mp[nval];
                                dp[nxt] = (dp[nxt] + 1LL * dp[x] * p[x][j]) % mod;
                            }
                        }
                    }
                }
            }
        }
        cout << dp[pos[3 * n][0]] << '\n';
    }

}