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

#include <algorithm>
#define rep(i, p, k) for (int i = (p); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define fi first
#define sc second
#ifndef DEBUG
#define debug(...)
#else
#include "debug.h"
#endif
using namespace std;
const int P = 1e9 + 7;

ll add(ll a, ll b) { return a + b >= P ? a + b - P : a + b; }
ll mul(ll a, ll b) { return a * b % P; }
const int NN = 4e6 + 13;

ll fastpow(ll x, ll n) {
  ll r = 1;
  for (; n; n >>= 1) {
    if (n & 1) r = mul(r, x);
    x = mul(x, x);
  }
  return r;
}

ll fac[NN], inv[NN], ifac[NN], ip2[NN];

// a solo, n in total
ll p_calc(int a, int n) {
  assert((n - a) % 2 == 0);
  int b = (n - a) / 2;
  return mul(fac[n], mul(ifac[n - a], mul(fac[2 * b], ip2[b])));
}

ll solve() {
  int n;
  cin >> n;
  vector<int> t(2 * n);
  for (auto& v : t) cin >> v;
  {
    int c0 = (int)count(all(t), 0);
    int c1 = (int)count(all(t), 1);
    int c2 = (int)count(all(t), 2);
    if (c0 == 2 * n || c2 == 2 * n) {
      return add(mul(n, p_calc(0, 4 * n - 2)),
                 mul(n, mul(n - 1, p_calc(2, 4 * n - 2))));
    }
    if (c0 != 0 && c2 != 0) return 0;
    if (c2) {
      for (auto& v : t)
        if (v == 2) v = 0;
      reverse(all(t));
      reverse(1 + all(t));
    }
    if (c1 == 2 * n) {
      return add(mul(2 * n, mul(n, mul(n - 1, p_calc(3, 4 * n - 3)))),
                 mul(2 * n, mul(n, p_calc(1, 4 * n - 3))));
    }
    {
      if(t.front() == 0) {
        int i = 0;
        while(t[i] == 0) i++;
        if(i % 2  == 1) return 0;
        rotate(t.begin(), t.begin() + i, t.end());
      } else if(t.back() == 1) {
        int i=2*n-1;
        while(t[i] == 1) i--;
        if(i % 2 == 0) return 0;
        rotate(t.begin(), t.begin() + i + 1, t.end());
      }
      rep(i, 0, 2 * n - 1) if (t[i] == 1 && t[i + 1] == 0 && i % 2 == 1) return 0;
      rep(i, 0, 2 * n - 1) if (t[i] == 0 && t[i + 1] == 1 && i % 2 == 0) return 0;
    }
  }
  return -1;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  fac[0] = 1;
  rep(i, 1, NN) fac[i] = mul(fac[i - 1], i);
  ifac[NN - 1] = fastpow(fac[NN - 1], P - 2);
  for (int i = NN - 2; i >= 0; i--) ifac[i] = mul(ifac[i + 1], i + 1);
  rep(i, 1, NN) inv[i] = mul(fac[i - 1], ifac[i]);
  ip2[0] = 1;
  rep(i, 1, NN) ip2[i] = mul(ip2[i - 1], (P + 1) / 2);
  rep(i, 0, NN) assert(mul(fac[i], ifac[i]) == 1);
  int Z;
  cin >> Z;
  while (Z--) {
    cout << solve() << '\n';
  }
  return 0;
}