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
#include <bits/stdc++.h>
#define MOD 1000000007
int T,N,a[2000009],b[2000009],p[4000009],ii[4000009],ss[2000009];
signed main(void) {
	scanf("%d",&T);
	p[0]=ii[0]=1;
	for(int i=1;i<=4000000;i++) {
		p[i]=1ll*p[i-1]*i%MOD;
		ii[i]=1ll*ii[i-1]*(MOD+1)/2%MOD;
	}
	while(T--) {
		scanf("%d",&N);
		int mi=2,ma=0;
		for(int i=1;i<=2*N;i++) {
			scanf("%d",&a[i]);
			mi=std::min(mi,a[i]);
			ma=std::max(ma,a[i]);
		}
		if(ma-mi==2) {
			printf("0\n");
			continue;
		}
		int ans=0;
		int cct=0;
		for(int j=1;j<2*N;j++) {
			if(a[j]!=a[j+1]) cct++;
		}
		if(a[2*N]!=a[1]) cct++;
		if(cct==0) {
			for(int i=1;i<=2*N;i++) ss[i]=2*N;
		} else {
			assert(cct%2==0);
			for(int j=1;j<=2*N;j++) {
				ss[j]=1;
			}
			for(int j=2*N;j>=1;j--) {
				if(a[j]==a[j%(2*N)+1]) {
					ss[j]=std::max(ss[j],ss[j%(2*N)+1]+1);
				}
			}
			for(int j=2*N;j>=1;j--) {
				if(a[j]==a[j%(2*N)+1]) {
					ss[j]=std::max(ss[j],ss[j%(2*N)+1]+1);
				}
			}
			bool gg=0;
			int sq=0;
			for(int j=1;j<=2*N;j++) {
				if(a[j]!=a[j%(2*N)+1]&&ss[j%(2*N)+1]%2==0) 
					gg=1; 
				if(a[j]!=a[j%(2*N)+1]) {
					sq+=ss[j%(2*N)+1];
//					printf("%d ",ss[j%(2*N)+1]);
				}
			}
			assert(sq==2*N);
//			printf("\n");
			if(gg) {
				printf("0\n");
				continue;
			}
		}
		if(cct==0) {
			if(a[1]==0||a[1]==2) {
				ans=(ans+1ll*N*p[4*N-2]%MOD*ii[2*N-1])%MOD;
				ans=(ans+1ll*N*(N-1)%MOD*p[4*N-2]%MOD*ii[2*N-2])%MOD;
			}
		}
		for(int i=1;i<=2*N;i++) {
			if(i%2==0&&(mi==0)) continue;
			if(i%2==1&&(ma==2)) continue;
			if(a[i]!=1) continue;
//			for(int j=1;j<=2*N;j++) {
//				b[j]=a[(j+2*N-i-1)%(2*N)+1];
//			}
//			b[2*N+1]=-1;
			int aq=i%(2*N)+1;
			if(cct>0) {
				if(ss[aq]%2&&a[aq]==a[i]) continue;
			}
		//	printf("!! %d\n",i);
/*			int la=1;
			bool gg=0;
			for(int j=2;j<=2*N+1;j++) {
				if(b[j]!=b[j-1]) {
					if(la>1&&(la%2==j%2)) {
						gg=1;
						break;
					}
					la=j;
				}
			}
			if(gg) continue;*/
			int ct=cct+1;
			if(a[aq]!=a[i]) ct--;
//			printf("??\n");
			int la=ss[aq];
			int cc1=N,cc2=N;
			//printf("%d %d\n",ct,la);
			//case 1 : hui dao yuan lai de shang mian
//			printf("%d %d %d\n",cc,cc2,la);
			ans=(ans+1ll*p[4*N-ct-1]*(ct/2)%MOD*ii[2*N-ct])%MOD;

			if(ct<=2*N-1) ans=(ans+1ll*p[4*N-ct-1]*(N-ct/2-(la/2))%MOD*ii[2*N-ct-1])%MOD;

			if(ct<=2*N-1) ans=(ans+1ll*p[4*N-ct-2]*(la/2)%MOD*(ct/2+1)%MOD*ii[2*N-ct-1])%MOD;

			if(ct<=2*N-2) ans=(ans+1ll*p[4*N-ct-2]*(la/2)%MOD*(N-ct/2-1)%MOD*ii[2*N-ct-2])%MOD;
		}
		//ans=1ll*ans*pw(2,N)%MOD;
		//sss[N]=(sss[N]+ans)%MOD;
		printf("%d\n",ans);
	}
//	for(int i=1;i<=6;i++) {
//		printf("%d %d %lld\n",i,sss[i],1ll*p[4*i]*ii[2*i]%MOD);
//	}
}