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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define st first
#define nd second
#define ld long double

ll M = 1e9+7;

vector<ll> fact (4e6+1, 1), pow2inv(4e6+1, 1);

ll powr(ll a, ll b) {
    if (b==0) {
        return 1;
    }
    ll x = powr(a, b/2);
    x = (x*x)%M;
    return b%2 ? (x*a)%M : x;
}

ll inv (ll a) {
    return powr(a, M-2);
}

void solve() {
    ll n;
    cin >> n;
    vector<ll> a (2*n, 0);
    bool w0 = 0, w1 = 0, w2 = 0;
    for (ll &i : a) {
        cin >> i;
        if (i==0) {
            w0=1;
        }
        if (i==1) {
            w1=1;
        }
        if (i==2) {
            w2=1;
        }
    }
    if (w0 && w2) {
        cout << 0 << '\n';
        return;
    }
    if (w1 && !(w0||w2)) {
        if (n==1) {
            cout << 2 << '\n';
            return;
        }
        ll ans = n*(4*n-3)%M;
        ll x = n*fact[4*n-4]%M*pow2inv[2*n-2]%M;
        ll y = n*(4*n-4)%M*(n-1)%M*(4*n-5)%M*fact[4*n-6]%M*pow2inv[2*n-3]%M;
        cout << ans*(x+y)%M*2%M << '\n';
        return;
    }
    if ((w0||w2)&&(!w1)) {
        if (n==1) {
            cout << 1 << '\n';
            return;
        }
        ll x = n*fact[4*n-2]%M*pow2inv[2*n-1]%M;
        ll y = n*(4*n-2)%M*(n-1)%M*(4*n-3)%M*fact[4*n-4]%M*pow2inv[2*n-2]%M;
        cout << (x+y)%M << '\n';
        return;
    }
    if (w2) {
        for (ll &i : a) {
            i %= 2;
        }
    }
    else {
        ll pom = a[2*n-1];
        for (ll i = 2*n-1; i > 0; i--) {
            a[i] = a[i-1];
        }
        a[0] = pom;
    }
    for (ll i = 0; i < 2*n; i++) {
        if (a[i] != a[(i+1)%(2*n)]) {
            if (a[i] != i%2) {
                cout << 0 << '\n';
                return;
            }
        }
    }
    ll l = 0;
    for (ll i = 0; i < 2*n; i++) {
        if (a[i]) {
            a.push_back(1);
            l++;
        }
        else {
            break;
        }
    }
    for (ll i = 0; i < 2*n; i++) {
        a[i] = a[i+l];
    }
    a.resize(2*n);
    reverse(a.begin(), a.end());
    l = 0;
    for (ll i = 0; i < 2*n; i++) {
        if (!a[i]) {
            a.push_back(0);
            l++;
        }
        else {
            break;
        }
    }
    for (ll i = 0; i < 2*n; i++) {
        a[i] = a[i+l];
    }
    a.resize(2*n);
    reverse(a.begin(), a.end());
    vector<ll> p;
    ll d = 1;
    for (ll i = 1; i < 2*n; i++) {
        if (a[i] != a[i-1]) {
            p.push_back(d);
            d = 1;
        }
        else {
            d++;
        }
    }
    p.push_back(d);
    ll m = p.size()/2;
    ll ans = 0;
    for (ll i = 0; i < m; i++) {
        ll in = i*2+1;
        ll w = p[(in+1)%(2*m)];
        ans += m*fact[4*n-2*m-1]%M*pow2inv[2*n-2*m]%M;
        //cout << ans << '\n';
        if (w/2 > 0) {
            ll x = w/2;
            ans += x*(m+1)%M*fact[4*n-2*m-2]%M*pow2inv[2*n-2*m-1]%M;
            //cout << ans << '\n';
            ans += x*(n-m-1)%M*fact[4*n-2*m-2]%M*pow2inv[2*n-2*m-2]%M;
            //cout << ans << '\n';
        }
        //cout << ans << '\n';
        if (n > m) {
            ans += (n-m-w/2)*fact[4*n-2*m-1]%M*pow2inv[2*n-2*m-1]%M;
        }
        //cout << ans << '\n';
        ans %= M;
        for (ll j = 0; j < p[in]/2; j++) {
            ll x = (p[in]-j*2-1)/2;
            ll y = 2*m+1;
            ans += m*fact[4*n-2*m-2]%M*pow2inv[2*n-2*m-1]%M;
            ans += (n-m-x)*fact[4*n-2*m-2]%M*pow2inv[2*n-2*m-2]%M;
            ans += x*(m+1)*fact[4*n-2*m-3]%M*pow2inv[2*n-2*m-2]%M;
            ans += x*(n-m-1)*fact[4*n-2*m-3]%M*pow2inv[2*n-2*m-3]%M;
            ans %= M;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (ll i = 1; i < 4e6+1; i++) {
        fact[i] = (fact[i-1]*i)%M;
    }
    pow2inv[4e6] = inv(powr(2, 4e6));
    for (ll i = 4e6 -1; i > 0; i--) {
        pow2inv[i] = (pow2inv[i+1]*2)%M;
    }
    ll t=1;
    cin >> t;
    for (ll i = 0; i < t; i++) {
        solve();
    }
}