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
#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1e9 + 7;
static const int MAXN = 1e6 + 5;

long long fact[MAXN];
long long pow2[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // precompute
    fact[0] = 1;
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
        pow2[i] = pow2[i-1] * 2 % MOD;
    }

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<int> a(2*n);
        for (int i = 0; i < 2*n; i++) cin >> a[i];

        bool ok = true;
        for (int i = 0; i < 2*n; i++) {
            if (a[i] + a[(i+1) % (2*n)] != 2) {
                ok = false;
                break;
            }
        }

        if (!ok) {
            cout << 0 << '\n';
        } else {
            cout << (pow2[n] * fact[n]) % MOD << '\n';
        }
    }

    return 0;
}