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
#!/usr/bin/env python3

precalc = {
  '00': 1,
  '10': 1,
  '11': 2,
  '1010': 24,
  '0010': 54,
  '1011': 114,
  '0000': 540,
  '1111': 720,
  '101010': 1080,
  '001010': 8640,
  '101011': 11160,
  '000010': 63000,
  '001110': 108360,
  '101111': 148680,
  '000000': 1701000,
  '111111': 2041200,
  '10101010': 80640,
  '00101010': 1260000,
  '10101011': 1441440,
  '00001010': 24494400,
  '00100010': 24494400,
  '00101110': 29484000,
  '00111010': 29484000,
  '10101111': 34020000,
  '10111011': 34473600,
  '00000010': 366735600,
  '00001110': 561330000,
  '00111110': 740955600,
  '10111111': 905612400,
  '00000000': 19070251200,
  '11111111': 21794572800
}

M, P = 4_000_009, 10**9 + 7

fac = [1] * M
for n in range(2, M):
  fac[n] = n * fac[n-1] % P

h = pow(2, -1, P)
hp = [1] * M
for n in range(1, M):
  hp[n] = h * hp[n-1] % P

def comps(n, k, hd):
  p = 2*n - (k-1 if hd else k)
  return fac[4*n-k] * hp[p] % P

def solve(n, v):
  assert len(v) == 2*n
  if max(v) == 2:
    v = [2-x for x in v[::-1]]
  if max(v) == 2:
    return 0
  if min(v) == 1:
    return n * n * (2*n-1) * fac[4*n-3] * hp[2*n-3] % P if n > 1 else 2
  if max(v) == 0:
    return n * (2*n-1) * fac[4*n-2] * hp[2*n-1] % P

  v += v

  i = 0
  while not (v[i] and not v[i-1]):
    i += 1
  if i%2 != 0:
    return 0

  k = i
  runs = []
  for j in range(i, i+2*n+1):
    if v[j] != v[k]:
      runs.append(j-k)
      k = j
  if any(m%2 == 0 for m in runs):
    return 0
  runs = [m//2 for m in runs]

  k = len(runs) // 2

  res = 0
  for i in range(k):
    # Case 1
    m = runs[2*i+1]
    res += m * ((k+1) * comps(n, 2*k+2, 1) + (n-k-1) * comps(n, 2*k+2, 0))
    res += k * comps(n, 2*k+1, 1) + (n-m-k) * comps(n, 2*k+1, 0)

    # Case 2
    m = runs[2*i]
    t = m*(m+1) // 2
    res += t * ((k+1) * comps(n, 2*k+3, 1) + (n-k-1) * comps(n, 2*k+3, 0))
    res += k*m * comps(n, 2*k+2, 1) + ((n-k)*m-t) * comps(n, 2*k+2, 0)
  res %= P

  if n <= 4:
    s = ''.join(map(str, v[:2*n]))
    for _ in range(n):
      if s in precalc:
        assert precalc[s] % P == res
      s = s[2:] + s[:2]

  return res

tc = int(input())
for _ in range(tc):
  n = int(input())
  v = list(map(int, input().split()))
  print(solve(n, v))