#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,O3") using namespace std; using i64 = long long; #define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define se second #define fi first #define pii pair<int, int> #define sz(x) (int)(x).size() const int MOD = 1e9 + 7; inline void solve(int n){ int card; auto inp = [&](vi &vec, vi &cnt) -> void { for(int i = 0; i < 2 * n; i++){ cin >> card; cnt[card]++; } for(int i = 1; i <= 3 * n; i++){ if(cnt[i] & 1){ vec.emplace_back(i); } } return; }; vi a, b, c, cnta(3 * n + 1), cntb(3 * n + 1), cntc(3 * n + 1); inp(a, cnta), inp(b, cntb), inp(c, cntc); int rounds = (sz(a) + sz(b) + sz(c)) / 2; // her turda sadece 1 kart discardlansa if(!rounds){ cout << "1\n"; return; } int ab = 0, bc = 0, ca = 0; for(int i = 0; i < sz(a); i++){ ab += cntb[a[i]]; } for(int i = 0; i < sz(b); i++){ bc += cntc[b[i]]; } for(int i = 0; i < sz(c); i++){ ca += cnta[c[i]]; } int r2 = rounds, ans = 0; vector<vector<vvi>> dp(2, vector<vvi>(r2 + 1, vvi(r2 + 1, vi(r2 + 1)))); //cout << "base: " << " ab: " << ab << " bc: " << bc << " ca: " << ca << " rounds: " << rounds << "\n"; dp[0][ab][bc][ca] = 1; for(int r = 0; r < rounds; r++){ for(int p = 0; p < 3; p++){ for(ab = 0; ab <= r2; ab++){ for(int bc = 0; bc <= r2 - ab; bc++){ for(int ca = 0; ca <= r2 - ab - bc; ca++){ if(p == 0){ if(ab + ca == 0){ dp[1][ab][bc][ca] = (dp[1][ab][bc][ca] + dp[0][ab][bc][ca]) % MOD; } // a -> b eşlemesiz, eşleme olmadığına göre a'daki ac'lerden birini verdim if(bc < r2 && ca > 0){ dp[1][ab][bc + 1][ca - 1] = (dp[1][ab][bc + 1][ca - 1] + ((dp[0][ab][bc][ca] * ca) % MOD)) % MOD; } // a -> b eşlemeli if(ab > 0){ dp[1][ab - 1][bc][ca] = (dp[1][ab - 1][bc][ca] + ((dp[0][ab][bc][ca] * ab) % MOD)) % MOD; } } else if(p == 1){ if(ab + bc == 0){ dp[1][ab][bc][ca] = (dp[1][ab][bc][ca] + dp[0][ab][bc][ca]) % MOD; } // b -> c eşlemesiz, eşleme olmadığına göre ca artacak, ab azalacak if(ab > 0 && ca < r2){ dp[1][ab - 1][bc][ca + 1] = (dp[1][ab - 1][bc][ca + 1] + ((dp[0][ab][bc][ca] * ab) % MOD)) % MOD; } // b -> c eşlemeli if(bc > 0){ dp[1][ab][bc - 1][ca] = (dp[1][ab][bc - 1][ca] + ((dp[0][ab][bc][ca] * bc) % MOD)) % MOD; } } else{ if(bc + ca == 0){ dp[1][ab][bc][ca] = (dp[1][ab][bc][ca] + dp[0][ab][bc][ca]) % MOD; } // c -> a eşlemesiz if(ab < r2 && bc > 0){ dp[1][ab + 1][bc - 1][ca] = (dp[1][ab + 1][bc - 1][ca] + ((dp[0][ab][bc][ca] * bc) % MOD)) % MOD; } // c -> a eşlemeli if(ca > 0){ dp[1][ab][bc][ca - 1] = (dp[1][ab][bc][ca - 1] + ((dp[0][ab][bc][ca] * ca) % MOD)) % MOD; } } } } } dp[1].swap(dp[0]); for(int ab = 0; ab <= r2; ab++){ for(int bc = 0; bc <= r2 - ab; bc++){ for(int ca = 0; ca <= r2 - ab - bc; ca++){ //if(dp[0][ab][bc][ca]) cout << "r: " << r << " ab: " << ab << " bc: " << bc << " ca: "<< ca << " dp: " << dp[0][ab][bc][ca] << "\n"; dp[1][ab][bc][ca] = 0; } } } } //ans = (ans + dp[0][0][0][0]) % MOD; } cout << dp[0][0][0][0] << "\n"; return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1, n; cin >> n >> t; while(t--){ solve(n); } return 0; }