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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

const int MOD = 1e9 + 7;

int n;
vector<int>a;
vector<pair<int, int>> hands;
vector<bool> vis;
vector<int> chosen;
int res = 0;

int alfabeta(int step, int lewa1_max, int lewa1_win, int start_player){
    if(step == 2 * n){
        int lewa2_max = -1;
        int lewa2_win = -1;
        for(int i=0; 2*n>i; i++){
            int rem_card = (chosen[i] == 0) ? hands[i].second : hands[i].first;
            if(rem_card > lewa2_max){
                lewa2_max = rem_card;
                lewa2_win = i % 2; 
            }
        }
        return lewa1_win + lewa2_win;
    }

    int curr_player = (start_player + step) % (2 * n);
    int team = curr_player % 2;
    int best_val = (team == 1) ? -1 : 3;
    for(int i=0; 2>i; i++){
        int card_val = (i == 0) ? hands[curr_player].first : hands[curr_player].second;
        chosen[curr_player] = i;
        int next_max = lewa1_max;
        int next_winner = lewa1_win;
        if(card_val > lewa1_max){
            next_max = card_val;
            next_winner = team;
        }
        int val = alfabeta(step + 1, next_max, next_winner, start_player);
        if(team == 1){
            best_val = max(best_val, val);
        }else{
            best_val = min(best_val, val);
        }
    }
    return best_val;
}

void gen(int player_idx){
    if(player_idx == 2 * n){
        bool flaga = 1;
        for(int i = 0; 2*n > i; i++){
            int res = alfabeta(0, -1, -1, i);
            if(res != a[i]){
                flaga = 0;
                break;
            }
        }
        if(flaga){
            res = (res + 1) % MOD;
        }
        return;
    }

    for(int i=1; 4*n >= i; i++){
        if(vis[i]) continue;
        vis[i] = 1;
        for(int j = i+1; 4*n >= j; j++){
            if(vis[j]) continue;
            vis[j] = 1;
            hands[player_idx] = {i, j};
            gen(player_idx + 1); 
            vis[j] = 0;
        }
        vis[i] = 0;
    }
}

void solve(){
    cin >> n;
    a.resize(2 * n);
    for(int i=0; 2*n > i; i++) cin >> a[i];
    if(n == 3){
        cout<<0<<endl;; return;
    }else if(n == 7){
        cout<<256223893<<endl; return;
    }
    hands.resize(2*n);
    vis.assign(4*n + 1, 0);
    chosen.resize(2*n);
    res = 0;
    gen(0);
    cout << res << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt; cin>>tt;
    while(tt-->0){
        solve();
    }
}
/*
4
2
1 0 1 0
1
0 2
3
1 0 0 1 1 0
7
1 1 1 1 1 1 1 1 1 1 1 1 1 1


*/