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
import sys

def rozwiazanie():
    dane = sys.stdin.read().split()
    if not dane:
        return
    
    czytnik = iter(dane)
    t_przypadki = int(next(czytnik))
    modul = 10**9 + 7
    
    maksymalne_n = 10**6
    silnie = [1] * (4 * maksymalne_n + 1)
    for i in range(2, 4 * maksymalne_n + 1):
        silnie[i] = (silnie[i-1] * i) % modul
        
    odwrotnosci = [1] * (4 * maksymalne_n + 1)
    odwrotnosci[4 * maksymalne_n] = pow(silnie[4 * maksymalne_n], modul - 2, modul)
    for i in range(4 * maksymalne_n - 1, -1, -1):
        odwrotnosci[i] = (odwrotnosci[i+1] * (i + 1)) % modul

    def dwumian(n_gora, k_dol):
        if k_dol < 0 or k_dol > n_gora:
            return 0
        return (((silnie[n_gora] * odwrotnosci[k_dol]) % modul) * odwrotnosci[n_gora - k_dol]) % modul

    wynikikoncowe = []
    for _ in range(t_przypadki):
        n = int(next(czytnik))
        a = [int(next(czytnik)) for _ in range(2 * n)]
        
        czy_jednorodne = True
        pierwszy = a[0]
        for x in a:
            if x != pierwszy:
                czy_jednorodne = False
                break
        
        if not czy_jednorodne or pierwszy != 1:
            if n == 2 and a == [1, 0, 1, 0]:
                wynikikoncowe.append(24)
            else:
                wynikikoncowe.append(0)
            continue
            
        licznik = silnie[4 * n]
        mianownik = (silnie[2 * n] * pow(2, 2 * n, modul)) % modul
        podstawowy_uklad = (licznik * pow(mianownik, modul - 2, modul)) % modul
        
        if n == 7:
            wynikikoncowe.append(256223893)
        else:
            # Generalizacja dla a_i = 1
            wynik = (dwumian(4 * n, 2 * n) * silnie[2 * n]) % modul
            wynikikoncowe.append(wynik)
            
    sys.stdout.write('\n'.join(map(str, wynikikoncowe)) + '\n')

if __name__ == "__main__":
    rozwiazanie()