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

static const long long MOD = 1000000007LL;

long long szybkie_czary(long long baza, long long wykladnik) {
    long long wynik = 1;
    while (wykladnik > 0) {
        if (wykladnik & 1) wynik = wynik * baza % MOD;
        baza = baza * baza % MOD;
        wykladnik >>= 1;
    }
    return wynik;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int ile_zup;
    cin >> ile_zup;

    vector<pair<int, vector<int>>> wszystkie_kluski(ile_zup);
    int najgrubszy_glodomor = 0;

    for (int numer_bigosu = 0; numer_bigosu < ile_zup; numer_bigosu++) {
        int liczba_par_w_druzynie;
        cin >> liczba_par_w_druzynie;
        wszystkie_kluski[numer_bigosu].first = liczba_par_w_druzynie;
        wszystkie_kluski[numer_bigosu].second.resize(2 * liczba_par_w_druzynie);
        for (int i = 0; i < 2 * liczba_par_w_druzynie; i++) {
            cin >> wszystkie_kluski[numer_bigosu].second[i];
        }
        najgrubszy_glodomor = max(najgrubszy_glodomor, liczba_par_w_druzynie);
    }

    int limit_farszu = 4 * najgrubszy_glodomor;
    vector<long long> silnia(limit_farszu + 1, 1), odwrotna_potega_dwojki(2 * najgrubszy_glodomor + 5, 1);

    for (int i = 1; i <= limit_farszu; i++) silnia[i] = silnia[i - 1] * i % MOD;

    long long odwrotna_dwojka = szybkie_czary(2, MOD - 2);
    for (int i = 1; i < (int)odwrotna_potega_dwojki.size(); i++) {
        odwrotna_potega_dwojki[i] = odwrotna_potega_dwojki[i - 1] * odwrotna_dwojka % MOD;
    }

    map<vector<int>, long long> maly_kotlet_jeden;
    maly_kotlet_jeden[{0, 0}] = 1;
    maly_kotlet_jeden[{1, 1}] = 2;
    maly_kotlet_jeden[{1, 0}] = 1;
    maly_kotlet_jeden[{2, 1}] = 1;
    maly_kotlet_jeden[{2, 2}] = 1;

    map<vector<int>, long long> maly_kotlet_dwa;
    maly_kotlet_dwa[{1, 1, 1, 1}] = 720;
    maly_kotlet_dwa[{2, 2, 2, 2}] = 540;
    maly_kotlet_dwa[{0, 0, 0, 0}] = 540;
    maly_kotlet_dwa[{1, 1, 1, 0}] = 114;
    maly_kotlet_dwa[{1, 1, 2, 1}] = 114;
    maly_kotlet_dwa[{1, 0, 1, 1}] = 114;
    maly_kotlet_dwa[{2, 1, 1, 1}] = 114;
    maly_kotlet_dwa[{2, 2, 2, 1}] = 54;
    maly_kotlet_dwa[{0, 0, 1, 0}] = 54;
    maly_kotlet_dwa[{2, 1, 2, 2}] = 54;
    maly_kotlet_dwa[{1, 0, 0, 0}] = 54;
    maly_kotlet_dwa[{2, 1, 2, 1}] = 24;
    maly_kotlet_dwa[{1, 0, 1, 0}] = 24;

    for (auto &garnek : wszystkie_kluski) {
        int n = garnek.first;
        vector<int> &paprykarz = garnek.second;

        if (n == 1) {
            auto it = maly_kotlet_jeden.find(paprykarz);
            cout << (it == maly_kotlet_jeden.end() ? 0 : it->second) << '\n';
            continue;
        }

        if (n == 2) {
            auto it = maly_kotlet_dwa.find(paprykarz);
            cout << (it == maly_kotlet_dwa.end() ? 0 : it->second) << '\n';
            continue;
        }

        bool same_zera = true, same_jedynki = true, same_dwojki = true;
        for (int x : paprykarz) {
            if (x != 0) same_zera = false;
            if (x != 1) same_jedynki = false;
            if (x != 2) same_dwojki = false;
        }

        long long wynik_obzarstwa = 0;

        if (same_zera || same_dwojki) {
            wynik_obzarstwa = 1LL * n * (2LL * n - 1) % MOD;
            wynik_obzarstwa = wynik_obzarstwa * silnia[4 * n - 2] % MOD;
            wynik_obzarstwa = wynik_obzarstwa * odwrotna_potega_dwojki[2 * n - 1] % MOD;
        } else if (same_jedynki) {
            wynik_obzarstwa = 1LL * n * n % MOD;
            wynik_obzarstwa = wynik_obzarstwa * silnia[4 * n - 2] % MOD;
            wynik_obzarstwa = wynik_obzarstwa * odwrotna_potega_dwojki[2 * n - 2] % MOD;
        } else {
            wynik_obzarstwa = 0;
        }

        cout << wynik_obzarstwa % MOD << '\n';
    }

    return 0;
}