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
#include <iostream>
#include <vector>
using namespace std;
int const max_N = 2000005;
long long const mod_P = 1000000007;
int seq[max_N];
long long poss_fixed[max_N];
int n;

int distance_between(int a, int b) {
	if (a < b) return b - a;
	else return 2 * n + b - a;
}

long long mod_pow(long long x, long long n) {
	if (n == 0) return 1;
	long long u = mod_pow(x, n / 2);
	u = (u * u) % mod_P;
	if (n % 2 == 1) u = (u * x) % mod_P;
	return u;
}

long long calc_inv_mod(long long a) {
	return mod_pow(a, mod_P - 2);
}

int main()
{
int cases;
cin >> cases;
bool has0;
bool has2;
for (int cases_i = 0; cases_i < cases; cases_i++){
	cin >> n;
	has0 = false;
	has2 = false;
	for (int i = 0; i < 2 * n; i++) {
		cin >> seq[i];
		if (seq[i] == 0) has0 = true;
		if (seq[i] == 2) has2 = true;
	}
	if (has0 && has2) {
		cout << 0 << "\n";
		continue;
	}
	poss_fixed[4 * n] = 1;
	for (int i = 1; i <= 4 * n; i++) {
		poss_fixed[4 * n - i] =  (poss_fixed[4 * n - i + 1] * i) % mod_P;
	}

	if (!has0 && !has2) {
		int count = (2 * n * (2 * n) * (2 * n - 1)) % mod_P;
		count = (((count * poss_fixed[3]) % mod_P) * mod_pow(2, (mod_P - 1) - 2 * n)) % mod_P;
		count = (2 * count) % mod_P;
		cout << count << "\n";
		continue;
	}
	bool A_adv = has2;
	seq[2 * n] = seq[0];
	vector<int> changes = vector<int>();
	for (int i = 0; i < 2 * n; i++) {
		if (seq[i] != seq[i+1]) {
			changes.push_back(i);
		}
	}
	if (changes.size() != 0) {
		changes.push_back(changes[0]);
		bool side = changes[0] % 2;
		bool is_wrong = false;
		for (int i = 1; i < changes.size() - 1; i++) {
			side = !side;
			if (side != changes[i] % 2) {
				is_wrong = true;
				break;
			}
		}
		if (A_adv) {
			if (((changes[0] + 1) % 2) != seq[changes[0]] - 1) is_wrong = true;
		}
		else {
			if (((changes[0] + 1)% 2) != seq[changes[0]]) is_wrong = true;
		}
		if (is_wrong) {
			cout << 0 << "\n";
			continue;
		}
		// seq[0]
		//if A_adv we have 0, 1
		long long count = 0;
		int k = (changes.size() - 1) / 2;
		for (int i = 0; i < changes.size() - 1; i++) {
			int inner_space = distance_between(changes[i + 1], changes[i]);
			int outer_space = distance_between(changes[i], changes[i + 1]);
			if (changes[i] % 2 == A_adv) { //cases 0 and B applicable
				count = (count + (inner_space - k + 1) * poss_fixed[2 * k + 1]) % mod_P; //case 0
				count = (count + ((outer_space - 1) *(2*n - k - 1) % mod_P) * poss_fixed[2 * k + 2]) % mod_P; // case B 
			}
			else { // cases F and FB applicable
				int l = inner_space - k + 1;
				int s = (outer_space - 1) / 2;
				count = (count + (2*(s * (l + s - 1)) % mod_P) * poss_fixed[2 * k + 2]) % mod_P;
				l = (outer_space - 1) / 2;
				count = (count + ((2 * l * (l + 1) * (2 * n - k - 1)) % mod_P) * poss_fixed[2 * k + 3]) % mod_P;
			}
		}
		count = (count * mod_pow(2, (mod_P - 1) + 2 * k - 2*n)) % mod_P;
		cout << count << "\n";
	}
	else {
		//SPECIAL CASE WHEN ONE SIDE DOMINATES. 
		int count = ((2 * n) * (2 * n - 1)) % mod_P;
		count = (count * poss_fixed[2] * mod_pow(2, (mod_P - 1) - 2*n)) % mod_P;
		cout << count << "\n";
	}
}
}