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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=4e6+9;
constexpr int Mod=1e9+7;
constexpr int inv2=(Mod+1)/2;

ll n,a[N],fac[N],ifac[N],ipw2[N];
ll ext[N],bg[N],ok[N],pre[N];

inline ll pw(ll x,ll p){
    ll res=1;
    for(;p;p>>=1,x=x*x%Mod)if(p&1)res=res*x%Mod;
    return res;
}

inline void Init(const int n){
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%Mod;
    ifac[n]=pw(fac[n],Mod-2);
    for(int i=n-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%Mod;
    ipw2[0]=1;
    for(int i=1;i<=n;i++)ipw2[i]=ipw2[i-1]*inv2%Mod;
}

inline ll C(const int x,const int y){
    if(x<y||y<0)return 0;
    return fac[x]*ifac[y]%Mod*ifac[x-y]%Mod;
}

void solve(){
    scanf("%lld",&n);
    int sta=0;
    for(int i=1;i<=n*2;i++)scanf("%lld",a+i),sta|=(1<<a[i]);
    if((sta&1)&&(sta&4)){puts("0");return;}
    if(sta==1||sta==4){
        ll ans=0;
        ll res=n*fac[4*n-2]%Mod*ipw2[2*n-1]%Mod;
        ans=(ans+res)%Mod;
        res=n*(n-1)%Mod*fac[4*n-2]%Mod*ipw2[2*n-2]%Mod;
        ans=(ans+res)%Mod;
        printf("%lld\n",ans);
        return;
    }
    if(sta==2){
        ll ans=0;
        ll res=n*n%Mod*fac[4*n-3]%Mod*ipw2[2*n-2]%Mod;
        ans=(ans+res)%Mod;
        res=n*n%Mod*(n-1)%Mod*fac[4*n-3]%Mod*ipw2[2*n-3]%Mod;
        ans=(ans+res)%Mod;
        ans=ans*2%Mod;
        printf("%lld\n",ans);
        return;
    }
    if(sta&1){
        for(int i=1;i<=n*2;i++)a[i]=2-a[i];
        ll v=a[1];
        for(int i=2;i<=n*2;i++)a[i-1]=a[i];
        a[n*2]=v;
    }
    for(int i=1;i<=n*2;i++)a[i+n*2]=a[i];
    fill_n(pre,n*4+2,0); fill_n(ext,n*4+2,0);
    fill_n(bg,n*4+2,0); fill_n(ok,n*4+2,0);
    for(int i=1;i<=n*4;i++){
        pre[i]=1;
        if(a[i]==a[i-1])pre[i]=pre[i-1]+1;
    }
    for(int i=n*4;i>=1;i--){
        ext[i]=1;
        if(i<n*4&&a[i+1]==a[i])ext[i]=ext[i+1]+1;
        if(a[i]!=a[i-1])bg[i]=1,ok[i]=(ext[i]&1);
        else ok[i]=1;
    }
    for(int i=1;i<=n*4;i++)bg[i]+=bg[i-1],ok[i]+=ok[i-1];
    ll ans=0;
    for(int i=n*2+1;i<=n*4;i++){
        if(a[i]==2)continue;
        if(i&1)continue;
        ll cnt=bg[i]-bg[i-2*n];
        if(a[i-2*n+1]==a[i-2*n])++cnt;
        if(cnt==2*n){
            ans=(ans+n*fac[2*n-1])%Mod;
            continue;
        }
        ll lst=ext[i-2*n+1];
        if(!(pre[i]&1))continue;
        ll p=i-pre[i];
        ll sok=ok[p]-ok[i-2*n];
        if(sok!=p-(i-2*n))continue;
        ll c1=lst/2,c2=cnt/2,c3=n-c1-c2;
        ans=(ans+c2*fac[4*n-cnt-1]%Mod*ipw2[2*n-cnt])%Mod;
        ans=(ans+c3*fac[4*n-cnt-1]%Mod*ipw2[2*n-cnt-1])%Mod;
        ans=(ans+c1*(c1+c3-1)%Mod*fac[4*n-cnt-2]%Mod*ipw2[2*n-cnt-2])%Mod;
        ans=(ans+c1*(c2+1)%Mod*fac[4*n-cnt-2]%Mod*ipw2[2*n-cnt-1])%Mod;
    }
    printf("%lld\n",ans);
}

int main(){
    int T;
    scanf("%d",&T);
    Init(4000000);
    while(T--)solve();
    return 0;
}