1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MXN = 4'000'000 + 7;
int f[MXN], inv[MXN];

int bin(int n, int k) {
    if (k > n) return 0;
    return f[n] * inv[k] % MOD * inv[n - k] % MOD;
}

int fp(int a, int n) {
    int r = 1;
    while (n) {
        if (n & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return r;
}

int32_t main()
{
    f[0] = 1;
    for (int i = 1; i < MXN; i++) f[i] = (f[i - 1] * i) % MOD;
    inv[MXN - 1] = fp(f[MXN - 1], MOD - 2);
    for (int i = MXN - 2; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % MOD;
    int inv_2 = fp(2, MOD - 2);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        vector<int>a(2 * n);
        array<array<int, 3>, 2> cnt{};
        for (int i = 0; i < 2 * n; i++) {
            cin >> a[i];
            if (i&1) cnt[1][2 - a[i]]++;
            else cnt[0][a[i]]++;
        }
        // jeden ma miec zbior {0, 1}, drugi ma miec {1, 2}
        if ((cnt[0][2] && cnt[1][2]) ||
            (cnt[0][0] && cnt[0][2]) || (cnt[1][0] && cnt[1][2]))
        {
            cout << "0\n";
            continue;
        }
        // nie ma 2 i nie ma 0
        if ((cnt[0][2] == 0 && cnt[1][2] == 0) && (cnt[0][0] == 0 && cnt[1][0] == 0)) {
            // jeden ma mx, drugi ma mx-1, mx-2
            // cout << "XD1" << endl;
            int z1 = bin(4 * n - 3, 2 * n - 1) * (f[2 * n] * fp(inv_2, n) % MOD) % MOD;  
            // cout << "XD2 " << bin(4 * n - 3, 2 * n - 1) << " " << f[2 * n] * fp(inv_2, n) % MOD << endl;
            int z2 = f[2 * n] * fp(inv_2, n) % MOD;
            // cout << "XD3 " << f[2 * n] << " " << z2 << endl;
            int ans = 2 * z1 * z2 % MOD;
            cout << ans << "\n";
            continue;
        }
        // nie ma 1
        if (cnt[0][1] == 0 && cnt[1][1] == 0) {
            // jeden ma mx, mx-1
            int z1 = bin(4 * n - 2, 2 * n - 2) * (f[2 * n] * fp(inv_2, n) % MOD) % MOD;
            int z2 = f[2 * n] * fp(inv_2, n) % MOD;
            int ans = z1 * z2 % MOD;
            cout << ans << "\n";
            continue;
        }

        vector<int> sk(2 * n);
        int nr = 0;
        bool bad = false;
        for (int i = 0; i < 2 * n; i++) {
            if (a[i] != 1 && !sk[i]) {
                ++nr;
                int p = i, len = -1;
                while (a[p] != 1) {
                    len++;
                    sk[p] = nr;
                    p = (p + 2 * n - 1) % (2 * n);
                }
                int k = i;
                while (a[k] != 1) {
                    len++;
                    sk[k] = nr;
                    k = (k + 1) % (2 * n);
                }
                if (len % 2 == 0)
                    bad = true;
            }
        }
        
        if (bad) {
            cout << "0\n";
            continue;
        }

        int pom = 0;
        for (int i = 0; i < 2 * n; i++) {
            int nt = (i + 1) % (2 * n);
            if (a[i] == 1 && a[nt] != 1) {
                pom++;
            }
        }

        // int ans = 
        cout << "0\n";

    }
}