#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG

#include "lib/debug.h"

#else
#define debug(...) 228
#endif


typedef long long ll;
typedef long double ld;

#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)

vector<int> read_vec(int n) {
    vector<int> v(n);
    for (int &t: v) cin >> t;
    return v;
}

template<typename T>
inline void upd_max(T &a, T b) {
    if (a < b) {
        a = b;
    }
}

template<typename T>
inline void upd_min(T &a, T b) {
    if (a > b) {
        a = b;
    }
}

template<int mod>
struct MInt {
    int x;

    constexpr MInt() : x{} {}

    constexpr MInt(ll x) : x{norm(x % getMod())} {}

    static int Mod;

    constexpr static int getMod() {
        if (mod > 0) {
            return mod;
        } else {
            return Mod;
        }
    }

    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }

    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }

    constexpr int val() const {
        return x;
    }

    explicit constexpr operator int() const {
        return x;
    }

    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }

    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }

    constexpr MInt &operator*=(MInt rhs) &{
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }

    constexpr MInt &operator+=(MInt rhs) &{
        x = norm(x + rhs.x);
        return *this;
    }

    constexpr MInt &operator-=(MInt rhs) &{
        x = norm(x - rhs.x);
        return *this;
    }

    constexpr MInt &operator/=(MInt rhs) &{
        return *this *= rhs.inv();
    }

    friend constexpr MInt power(MInt a, ll b) {
        MInt res = 1;
        for (; b; b /= 2, a *= a) {
            if (b % 2) {
                res *= a;
            }
        }
        return res;
    }

    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }

    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }

    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }

    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }

    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }

    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }

    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<int mod>
string to_string(const MInt<mod> &number) {
    return to_string(number.val());
}

template<int V, int mod>
constexpr MInt<mod> CInv = MInt<mod>(V).inv();

template<>
int MInt<0>::Mod = 0;

constexpr int mod = (int) 1e9 + 7;
using Mint = MInt<mod>;


struct Comb {
    int n;
    vector<Mint> _fac;
    vector<Mint> _invfac;
    vector<Mint> _inv;

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}

    Comb(int n) : Comb() {
        init(n);
    }

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    Mint fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }

    Mint invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }

    Mint inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }

    Mint cnk(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

const int maxN = 2e6 + 10;
Mint inv2[maxN];
void solve() {
    int n;
    cin >> n;
    vector<int> a(2 * n);
    FOR(i, 0, 2 * n) cin >> a[i];
    inv2[0] = 1;
    Mint val = (mod + 1) / 2;
    FOR(i, 1, 2 * n + 1) inv2[i] = val * inv2[i - 1];
    if (*min_element(a.begin(), a.end()) == 0) {
        for (auto &it: a) it = 2 - it;
        rotate(a.begin(), a.begin() + 1, a.end());
    }
    if (*min_element(a.begin(), a.end()) == 0) {
        cout << 0 << '\n';
        return;
    }
    Mint ans = 0;
    int cnt[2] = {0, 0};
    cnt[a[0] - 1]++;
    bool ch = false;
    FOR(i, 1, 2 * n) {
        if (a[i] != a[i - 1]) {
            cnt[a[i] - 1]++;
            ch = true;
        }
    }
    if (a[0] == a[2 * n - 1] && ch) {
        cnt[a[0] - 1]--;
    }
    if (cnt[0] && cnt[1]) assert(cnt[0] == cnt[1]);
    vector<int> lens[2];
    FOR(i, 0, 2 * n) {
        if (a[i] != a[(i + 1) % (2 * n)]) {
            int s = (i + 1) % (2 * n);
            for (int x = s;; x++) {
                if (a[x % (2 * n)] != a[s]) {
                    lens[a[s] - 1].emplace_back(x - s);
                    break;
                }
            }
        }
    }
    if (lens[0].empty()) {
        assert(lens[1].empty());
        lens[a[0] - 1] = {2 * n};
    }


    bool ok = true;
    FOR(i, 0, 2 * n) {
        if (a[i] != a[(i + 1) % (2 * n)]) {
            if ((a[i] == 1) != (i % 2 == 1)) {
                ok = false;
                break;
            }
        }
        //cand for 4n - k
    }
    if (!ok) {
        cout << 0 << '\n';
        return;
    }

    auto f = [&](int a, int b, int tot_x, int tot_y) {
        //a of first parity, b of second are occupied
        if (a > tot_x || b > tot_y || a < 0 || b < 0) return Mint(0);
        return comb.fac(2 * tot_x + 2 * tot_y - a - b) * inv2[tot_x - a + tot_y - b];
    };

    auto finish = [&](int a, int b) {
        //I have a cards of even, b cards of odd (on distinct) poses
        //I want to put one more guy on even ones
        return a * f(a - 1, b, n - 1, n) + (n - a) * f(a + 1, b, n, n);
    };
    FOR(k, 1, 2 * n + 1) {
        int cnt1 = 0;
        int cnt2 = 0;
        if (k % 2 == 1) {
            if (k == 1) {
                cnt1 = 0;
                cnt2 = 1;
            } else {
                cnt1 = k / 2;
                cnt2 = k / 2;
            }
        } else {
            if (k == 2) {
                cnt1 = 1;
                cnt2 = 0;
            } else {
                cnt1 = k / 2 - 1;
                cnt2 = k / 2 - 1;
            }
        }

        if (cnt1 == cnt[0] && cnt2 == cnt[1]) {
            //k >= 3
            if (k >= 3) {
                if (k % 2 == 1) {
                    assert(cnt1 >= 1 && cnt2 >= 1);
                    int S = 0;
                    FOR(i, 0, 2 * n) {
                        if (a[i] == 2 && i % 2 == 1) S++;
                    }
                    ans += finish(cnt1 + 1, cnt1) * S;
                } else {
                    assert(cnt1 >= 1 && cnt2 >= 1);
                    for (int z: lens[0]) {
                        assert(z % 2 == 1);
                        Mint ways = 0;
                        FOR(x, 0, z) {
                            if (x % 2 == 1) {
                                ways += x / 2 + 1;
                            }
                        }
                        ans += ways * finish(cnt1 + 1, cnt1 + 1);
                    }
                }
            } else {
                if (k == 1) {
                    ans += n * finish(1, 0);
                } else {
                    assert(k == 2);
                    ans += n * Mint(n) * finish(1, 1);
                }
            }
        }


        //color[4n - k + 1] != color[4n - k] and fits
        if (k % 2 == 1) {
            if (k == 1) {
                //ne bywaet
                cnt1 = -1;
                cnt2 = -1;
            } else {
                cnt1 = k / 2;
                cnt2 = k / 2;
            }
        } else {
            cnt1 = k / 2;
            cnt2 = k / 2;
        }

        if (cnt1 == cnt[0] && cnt2 == cnt[1]) {
            assert(k > 1);
            if (k % 2 == 1) {
                //put max
                for (int z: lens[0]) {
                    assert(z % 2 == 1);
                    Mint ways = (z - 1) / 2;
                    int lft = (2 * n - z);
                    int P = (lft + 1) / 2;
                    assert(P >= cnt1);
                    ans += ways * (P - cnt1) * f(cnt1 + 1, cnt1 + 1, n, n);
                    ans += ways * cnt1 * f(cnt1 - 1, cnt1 + 1, n - 1, n);

                    Mint ways2 = 0;
                    FOR(i, 0, z - 1) {
                        if (i % 2 == 0) {
                            ways2 += i / 2;
                        }
                    }
                    ans += ways2 * f(cnt1 + 1, cnt1 + 1, n, n);
                }
            } else {
                for (int z: lens[1]) {
                    assert(z % 2 == 1);
                    int lft = (2 * n - z + 1);
                    int P = (lft) / 2;
                    assert(P >= cnt1);
                    ans += (P - cnt1) * f(cnt1 + 1, cnt1, n, n);
                    ans += cnt1 * f(cnt1 - 1, cnt1, n - 1, n);
                }
            }
        }
    }
    if (*max_element(a.begin(), a.end()) == 1) {
        ans *= 2;
    }
    cout << ans << '\n';

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) solve();
    return 0;
}