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
123
124
125
126
127
128
129
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
const ll m=1e9+7,hf=(m+1)/2;
ll pw(ll a,ll b=m-2)
{
	ll r=1;
	while(b)
	{
		if(b&1) r=r*a%m;
		a=a*a%m;
		b>>=1;
	}
	return r;
}
ll jc[4000006];
ll ph[4000006];
ll jy[4000006];
ll C(int a,int b)
{
	if(b<0||b>a) return 0;
	return jc[a]*jy[b]%m*jy[a-b]%m;
}
int a[2000006];
void sl()
{
	int n;
	cin>>n;
	bool h2=0,h0=0,h1=0;
	for(int i=0;i<n*2;i++) cin>>a[i],h2|=a[i]==2,h0|=a[i]==0,h1|=a[i]==1;
	if(!h2&&!h0)
	{
		cout<<2*C(n*4-3,n*2-1)*jc[n*2]%m*jc[n*2]%m*ph[n*2]%m<<'\n';
		return;
	}
	if(h2&&h0)
	{
		cout<<"0\n";
		return;
	}
	if(h2)
	{
		for(int i=0;i<n*2;i++) a[i]=2-a[i];
		rotate(a,a+1,a+n*2);
	}
	if(!h1)
	{
		cout<<C(n*4-2,n*2)*jc[n*2]%m*jc[n*2]%m*ph[n*2]%m<<'\n';
		return;
	}
	vector<int> ad;
	for(int i=0;i<n*2;i++) if(a[i]!=a[(i+1)%(n*2)]) ad.push_back(i);
	if(a[0]==0) rotate(ad.begin(),++ad.begin(),ad.end());
	int k=ad.size()/2;
//	for(int i:ad) cout<<i<<' ';
//	cout<<endl;
	for(int i=0;i<k*2;i++) if(ad[i]%2!=i%2)
	{
		cout<<"0\n";
		return;
	}
	ll ans=0;
	for(int i=0;i<k*2;i++)
	{
		ll g=(ad[(i+1)%(k*2)]+n*2-ad[i])%(n*2);
		ll div,plc;
		if(i%2==0)
		{
			div=C(n*4-k*2-1,n*2-k);
			plc=jc[2*n-k]*jc[2*n-k]%m*ph[2*n-2*k]%m;
			if(k<n) plc+=m-g/2*jc[2*n-k]%m*jc[2*n-k-1]%m*ph[2*n-2*k-1]%m;
//			cout<<"O "<<div<<' '<<plc<<"  "<<g<<' '<<jc[2*n-k]*jc[2*n-k]%m*ph[2*n-2*k]%m<<' '<<g/2*jc[2*n-k]%m*jc[2*n-k-1]%m*ph[2*n-2*k-1]%m<<endl;
			ans+=div*plc%m;
			div=C(n*4-k*2-2,n*2-k);
			if(k<n) plc=g/2*jc[2*n-k]%m*jc[2*n-k-1]%m*ph[2*n-2*k-1]%m;
			else plc=0;
//			cout<<"O "<<div<<' '<<plc<<endl;
			ans+=div*plc%m;
		}
		else
		{
			div=C(n*4-k*2-3,n*2-k-1);
			if(k<n) plc=(g+1)*(g-1)/8%m*jc[2*n-k-1]%m*jc[2*n-k-1]%m*ph[2*n-2*k-2]%m;
			else plc=0;
//			cout<<"O "<<div<<' '<<plc<<endl;
			ans+=div*plc%m;
			div=C(n*4-k*2-2,n*2-k-1);
			if(k<n) plc=g/2*jc[2*n-k]%m*jc[2*n-k-1]%m*ph[2*n-2*k-1]%m;
			else plc=0;
			if(k<n) plc+=m-(g+1)*(g-1)/8%m*jc[2*n-k-1]%m*jc[2*n-k-1]%m*ph[2*n-2*k-2]%m;
//			cout<<"O "<<div<<' '<<plc<<endl;
			ans+=div*plc%m;
		}
//		cout<<"E "<<ans<<endl;
	}
	cout<<ans%m<<endl;
}
int main()
{
	jc[0]=1;
	ph[0]=1;
	for(int i=1;i<=4000000;i++) jc[i]=jc[i-1]*i%m,ph[i]=ph[i-1]*hf%m;
	jy[4000000]=pw(jc[4000000]);
	for(int i=3999999;i>=0;i--) jy[i]=jy[i+1]*(i+1)%m;
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) sl();
	return 0;
}/*3
2
1 0 1 1
2
1 0 1 0
2
1 0 1 1
*/