#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator<<(auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
auto operator<<(auto &o, auto a) -> decltype(all(a), o);
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", [](auto... arg_) { (( cerr << arg_ << ", " ), ...) << '\n'; }(x)
#else
#define deb(...) 0
#endif
#define deb(...) 0

const int P = 1e9 + 7, phiP = P - 1;
struct mint {
    int x = 0;
    mint operator+(mint o) const {return {x + o.x >= P ? x + o.x - P : x + o.x}; }
    mint operator-(mint o) const {return {x < o.x ? x - o.x + P : x - o.x}; }
    mint operator+() const {return *this; }
    mint operator-() const {return {x ? P - x : 0}; }
    mint operator*(mint o) const {return {int(ll(x) * o.x % P)}; }
    mint & operator+=(mint o) {return *this = *this + o; }
    mint & operator-=(mint o) {return *this = *this - o; }
    mint & operator*=(mint o) {return *this = *this * o; }
    mint pow(ll e) const {
        mint ret{1}, b(*this);
        for (; e; e >>= 1) {
            if (e & 1)
                ret *= b;
            b *= b;
        }
        return ret;
    }
};

auto &operator<<(auto &os, mint m) {
    return os << m.x - (2 * m.x >= P && &os == &cerr ? P : 0);
}

array<mint, int(4e6) + 6> fact, ifact, invs, pows2, ipows2;

auto initmint = [](){
    fact[0] = ifact[0] = fact[1] = ifact[1] = invs[1] = mint{1};
    fwd(i, 2, sz(fact)) {
        invs[i] = -mint{P / i} * invs[P % i];
        fact[i] = fact[i-1] * mint{i};
        ifact[i] = ifact[i-1] * invs[i];
    }
    pows2[0] = ipows2[0] = mint{1};
    fwd(i, 1, sz(fact)) {
        pows2[i] = pows2[i-1] * mint{2};
        ipows2[i] = ipows2[i-1] * invs[2];
    }
    return 0;
}();

mint ncr(int n, int r) {
    return 0 <= r && r <= n ? fact[n] * ifact[r] * ifact[n - r] : mint{0};
}
mint fallfac(int from, int cnt) {
    assert(from >= cnt);
    return fact[from] * ifact[from - cnt];
}

// // pierwszy gracz to potyczkowicz, odp to punkty algo
// map<vector<array<int, 2>>, int> score_cache;
// int score(const vector<array<int, 2>> &vec) {
//     if (auto it = score_cache.find(vec); it != score_cache.end())
//         return it->second;

//     assert(sz(vec) % 2 == 0);

//     auto rec = [&](this auto &self, int id, pii k0, pii k1) -> int {
//         if (id == sz(vec))
//             return k0.nd + k1.nd;

//         pii h0{vec[id][0], id&1}, h1{vec[id][1], id&1};

//         int A = self(id+1, max(k0, h0), max(k1, h1));
//         int B = self(id+1, max(k0, h1), max(k1, h0));

//         if (id&1) return max(A, B);
//         return min(A, B);
//     };

//     return score_cache[vec] = rec(0, pii{-1, 0}, pii{-1, 0});
// }

// map<vi, int> bruteNC(int n) {
//     deb(n);
//     assert(n % 2 == 0);
//     vector<array<int, 2>> cards(n);
//     int* cards_begin = &cards[0][0];
//     iota(cards_begin, cards_begin + 2*n, 0);

//     map<vi, int> mp;
//     vi scoreStart(n);

//     do {
//         bool ok = true;
//         for (auto [a, b] : cards) if (a < b) ok = false;
//         if (!ok) continue;

//         for (int i = 0; i < n; i += 2) {
//             scoreStart[i] = score(cards);
//             rotate(cards.begin(), cards.begin() + 1, cards.end());
//             scoreStart[i+1] = 2-score(cards);
//             rotate(cards.begin(), cards.begin() + 1, cards.end());
//         }

//         if (scoreStart == vi{2, 2, 2, 1})
//             deb(cards);

//         mp[scoreStart]++;

//     } while (next_permutation(cards_begin, cards_begin + 2*n));

//     deb(n);
//     deb(mp);

//     return mp;
// }

// map<int, map<vi, int>> bruteCache;
// int brute(vi a) {
//     if (!bruteCache.count(sz(a)))
//         bruteCache[sz(a)] = bruteNC(sz(a));
//     return bruteCache[sz(a)][a];
// }

mint podziel2(int k) {
    assert(k >= 0);
    return fact[k*2] * ipows2[k];
}

mint solveKer(vi a) { // tylko 12
    int n = sz(a); // ppl
    assert(n % 2 == 0);

    int c0 = (int)count(all(a), 0), c1 = (int)count(all(a), 1), c2 = (int)count(all(a), 2);
    assert(!c0);
    if (!c1) { // ...XX
        mint karty = ncr(2*n-2, n-2);
        return podziel2(n/2).pow(2) * karty;
    }
    if (!c2) { // ...YYX
        mint karty = ncr(2*n-3, n-1);
        return podziel2(n/2).pow(2) * karty;
    }
    assert(c1 && c2);

    deb(a);

    rep(i, n) a.pb(a[i]);
    fwd(i, 1, sz(a) - 1) {
        // jeśli potyczkowik przegrywa lub algorytmik przegrywa
        if ((i%2 == 0 && a[i] == 2) || (i%2 == 1 && a[i] == 1)) {
            if (a[i] != a[i-1] || a[i] != a[i+1])
                return {};
        }
    }
    int G = 0;
    rep(i, n) if (a[i] == 1 && a[i+1] == 2) ++G;
    assert(G > 0);

    vi nxt1(sz(a)), nxt2(sz(a));
    for (int i = sz(a) - 1; i >= 0; --i) {
        nxt1[i] = a[i] == 1 ? i : (i+1 < sz(a) ? nxt1[i+1] : sz(a));
        nxt2[i] = a[i] == 2 ? i : (i+1 < sz(a) ? nxt2[i+1] : sz(a));
    }

    mint tot;

    deb(a, G, nxt1, nxt2);

    for (int R = n+1; R < sz(a); R += 2) {
        int L = R - (n-1);

        deb(L, R);

        if (a[R] == 1) {
            { // ...YXYXYX, Y
                deb("case I");
                mint karty = ncr(2*n - (G+1) - (G+2), n - (G+1));
                int cfy = (nxt2[L] - L + 1) / 2;
                if (cfy) {
                    mint waysY = mint{cfy} * fallfac(n - (G+1), G+1) * podziel2(n/2 - (G+1));
                    mint waysX = fallfac(n - (G+1), G+1) * podziel2(n/2 - (G+1));
                    mint here = karty * waysY * waysX;
                    tot += here;
                    deb("I", L, R, here);
                }
            }
            { // ...XYXYX Y po prawej
                deb("case II");
                mint karty = ncr(2*n - (G+1) - (G+1), n - (G+1));
                mint waysY;
                { // Y duplikacja
                    waysY += mint{G} * fallfac(n - (G+1), G-1) * podziel2(n/2 - G);
                    int cg = (R - nxt2[L]) / 2 - G;
                    if (cg) {
                        waysY += mint{cg} * fallfac(n - (G+1), G+1) * podziel2(n/2 - (G+1));
                    }
                }
                mint waysX = fallfac(n - (G+1), G+1) * podziel2(n/2 - (G+1));
                mint here = karty * waysY * waysX;
                tot += here;
                deb("II", L, R, here);
            }
        }
        else if (a[R-1] == 1) {
            assert(a[R] == 2);
            { // ...XYXYXYX, X
                deb("case III");
                mint karty = ncr(2*n - G - (G+2), n - G);
                int cfx = (nxt1[L] - L + 1) / 2;
                if (cfx) {
                    mint waysX = mint{cfx} * fallfac(n - (G+1), G+1) * podziel2(n/2 - (G+1));
                    mint waysY = fallfac(n - G, G) * podziel2(n/2 - G);
                    mint here = karty * waysY * waysX;
                    tot += here;
                    deb("III", L, R, karty, cfx, waysX, waysY, here);
                }

            }
            { // ...YXYXYXYX, X po prawej
                deb("case IV");
                mint karty = ncr(2*n - (G+1) - G, n - (G+1));
                mint waysY = fallfac(n - G, G) * podziel2(n/2 - G);
                mint waysX;
                {
                    waysX += mint{G} * fallfac(n - (G+1), G-1) * podziel2(n/2 - G);
                    int cg = (R - nxt1[L] + 1) / 2 - G;
                    if (cg) {
                        waysX += mint{cg} * fallfac(n - (G+1), G+1) * podziel2(n/2 - (G+1));
                    }
                }
                mint here = karty * waysY * waysX;
                deb("IV", L, R, here);
                tot += here;
            }
        }
    }

    deb(a, tot);

    return tot;
}

mint solve(vi a) {
    a.pb(a[0]);
    a.erase(a.begin());

    int c0 = (int)count(all(a), 0), c2 = (int)count(all(a), 2);

    mint ans;
    if (!c0) {
        mint h = solveKer(a);
        ans += h;
    }
    if (!c2) {
        a.pb(a[0]);
        a.erase(a.begin());
        for (int &i : a) i = 2 - i;
        mint h = solveKer(a);
        ans += h;
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    vi a(2*n);
    rep(i, 2*n) cin >> a[i];

    auto ans = solve(a);
    // {
    //     int bruted = brute(a);
    //     if (bruted != ans.x) {
    //         deb(a);
    //         deb(bruted, ans);
    //         exit(-1);
    //     }
    // }
    cout << ans.x << '\n';
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    int z = 1;
    cin >> z;
    rep(_, z) solve();

    cout << flush;
    _Exit(0);
}