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
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 4e6 + 9, Mod = 1e9 + 7, inv2 = (Mod + 1) / 2;
ll n, a[N], fac[N], ifac[N], ipw2[N];
ll pw(ll x, ll p) {
    ll res = 1;
    while(p) {
        if(p & 1) res = res * x % Mod;
        x = x * x % Mod, p >>= 1;
    }
    return res;
}
void Init(ll n) {
    fac[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % Mod;
    ifac[n] = pw(fac[n], Mod - 2);
    per(i, n - 1, 0) ifac[i] = ifac[i + 1] * (i + 1) % Mod;
    ipw2[0] = 1;
    rep(i, 1, n) ipw2[i] = ipw2[i - 1] * inv2 % Mod;
}
ll C(ll x, ll y) {
    if(x < y || y < 0) return 0;
    return fac[x] * ifac[y] % Mod * ifac[x - y] % Mod;
}
ll ext[N], bg[N], ok[N], pre[N];
void solve() {
    n = read();
    ll sta = 0;
    rep(i, 1, n * 2) a[i] = read(), sta |= (1 << a[i]);
    if((sta & 1) && (sta & 4)) return puts("0"), void();
    if(sta == 1 || sta == 4) {
        ll ans = 0;
        // (4n, 4n - 1) 同一个人
        ll res = n * fac[4 * n - 2] % Mod * ipw2[2 * n - 1] % Mod;
        ans = (ans + res) % Mod;
        // (4n, 4n - 1) 不同人
        res = n * (n - 1) % Mod * fac[4 * n - 2] % Mod * ipw2[2 * n - 2] % Mod;
        ans = (ans + res) % Mod;
        write(ans), putchar('\n');
        return ;
    }
    if(sta == 2) {
        ll ans = 0;
        // 有 4n, 无 4n - 1，无 4n - 2
        ll res = n * n % Mod * fac[4 * n - 3] % Mod * ipw2[2 * n - 2] % Mod;
        ans = (ans + res) % Mod;
        res = n * n % Mod * (n - 1) % Mod * fac[4 * n - 3] % Mod * ipw2[2 * n - 3] % Mod;
        ans = (ans + res) % Mod;
        ans = ans * 2 % Mod;
        write(ans), putchar('\n');
        return ;
    }
    if(sta & 1) {
        rep(i, 1, n * 2) a[i] = 2 - a[i];
        ll v = a[1];
        rep(i, 2, n * 2) a[i - 1] = a[i];
        a[n * 2] = v;
    }
    rep(i, 1, n * 2) a[i + n * 2] = a[i];
    rep(i, 0, n * 4 + 1) pre[i] = ext[i] = bg[i] = ok[i] = 0;
    rep(i, 1, n * 4) {
        pre[i] = 1;
        if(a[i] == a[i - 1]) pre[i] = pre[i - 1] + 1;
    }
    per(i, n * 4, 1) {
        ext[i] = 1;
        if(i < n * 4 && a[i + 1] == a[i]) ext[i] = ext[i + 1] + 1;
        if(a[i] != a[i - 1]) bg[i] = 1, ok[i] = (ext[i] & 1);
        else ok[i] = 1;
    }
    // rep(i, 1, n * 4) cout << a[i] << " ";
    // cout << endl;
    // rep(i, 1, n * 4) cout << bg[i] << " ";
    // cout << endl;
    // rep(i, 1, n * 4) cout << ok[i] << " ";
    // cout << endl;
    rep(i, 1, n * 4) bg[i] += bg[i - 1], ok[i] += ok[i - 1];
    ll ans = 0;
    rep(i, n * 2 + 1, n * 4) {
        if(a[i] == 2) continue;
        if(i & 1) continue;
        ll cnt = bg[i] - bg[i - 2 * n];
        if(a[i - 2 * n + 1] == a[i - 2 * n]) ++cnt;
        if(cnt == 2 * n) {
            // 取决于剩下的 max
            ans = (ans + n * fac[2 * n - 1]) % Mod;
            continue;
        }
        ll lst = ext[i - 2 * n + 1];
        // if(!(lst & 1)) continue;
        if(!(pre[i] & 1)) continue;
        ll p = i - pre[i];
        ll sok = ok[p] - ok[i - 2 * n];
        if(sok != p - (i - 2 * n)) continue;
        ll c1 = lst / 2, c2 = cnt / 2, c3 = n - c1 - c2;
        // x 直接在后面了
        ans = (ans + c2 * fac[4 * n - cnt - 1] % Mod * ipw2[2 * n - cnt]) % Mod;
        ans = (ans + c3 * fac[4 * n - cnt - 1] % Mod * ipw2[2 * n - cnt - 1]) % Mod;
        // 在前面，然后 x-1 补刀
        ans = (ans + c1 * (c1 + c3 - 1) % Mod * fac[4 * n - cnt - 2] % Mod * ipw2[2 * n - cnt - 2]) % Mod;
        ans = (ans + c1 * (c2 + 1) % Mod * fac[4 * n - cnt - 2] % Mod * ipw2[2 * n - cnt - 1]) % Mod;
        // cout << ans << endl;
    }
    write(ans), putchar('\n');
}
bool Med;
int main() {
    // freopen("B.in", "r", stdin);
    // freopen("B2.out", "w", stdout);
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    ll T = read();
    Init(4e6);
    while(T--) solve();
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}