#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; const int MX = 300 + 5; int dp[3][MX][MX][MX][2], pairs; // dp[p][ab][bc][ca][no_discard] inline int calc_dp(int p, int ab, int bc, int ca, bool discards){ if(ab < 0 || bc < 0 || ca < 0 || ab > MX || bc > MX || ca > MX) return 0ll; if(dp[p][ab][bc][ca][discards]) return dp[p][ab][bc][ca][discards]; if(!ab && !bc && !ca) return dp[p][ab][bc][ca][discards] = 1ll; int nxt = (p + 1) % 3; if(p == 0){ if(ab + ca == 0){ dp[p][ab][bc][ca][discards] = calc_dp(nxt, ab, bc, ca, false); } // a -> b eşlemeli int add = (ab * calc_dp(nxt, ab - 1, bc, ca, true)) % MOD; dp[p][ab][bc][ca][discards] = (dp[p][ab][bc][ca][discards] + add) % MOD; // a -> b eşlemesiz add = (ca * calc_dp(nxt, ab, bc + 1, ca - 1, false)) % MOD; dp[p][ab][bc][ca][discards] = (dp[p][ab][bc][ca][discards] + add) % MOD; } else if(p == 1){ if(ab + bc == 0){ dp[p][ab][bc][ca][discards] = calc_dp(nxt, ab, bc, ca, discards); } // b -> c eşlemeli dp[p][ab][bc][ca][discards] = (bc * calc_dp(nxt, ab, bc - 1, ca, true)) % MOD; // b -> c eşlemesiz int add = (ab * calc_dp(nxt, ab - 1, bc, ca + 1, discards)) % MOD; dp[p][ab][bc][ca][discards] = (dp[p][ab][bc][ca][discards] + add) % MOD; } else{ // yeni tura başlıyorum discardı sıfırlamalıyım // c -> a eşlemeli dp[p][ab][bc][ca][discards] = (ca * calc_dp(nxt, ab, bc, ca - 1, false)) % MOD; if(discards){ if(bc + ca == 0){ dp[p][ab][bc][ca][discards] = (dp[p][ab][bc][ca][discards] + calc_dp(nxt, ab, bc, ca, false)) % MOD; } // c -> a eşlemesiz int add = (bc * calc_dp(nxt, ab + 1, bc - 1, ca, false)) % MOD; dp[p][ab][bc][ca][discards] = (dp[p][ab][bc][ca][discards] + add) % MOD; } } return dp[p][ab][bc][ca][discards]; } 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); pairs = (sz(a) + sz(b) + sz(c)) / 2; // pairs'den küçük eşit round sürdüğünde oyun discardsız hiçbir tur geçmiyor 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]]; } cout << calc_dp(0, ab, bc, ca, false) << "\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; }