int a[N],b[N],d[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int sum=0;
    for(int i=1;i<=n;i++){
        b[i]=read();
        d[i]=a[i]-b[i];
        sum+=d[i];
    }
    if(sum!=0){
        cout<<-1<<'\n';
        return ;
    }
    vector<int>ansx,ansy;
    for(int i=1;i<=n;i++){
        while(d[i]>0){
            d[i]--;
            ansy.push_back(i);
            for(int j=1;j<=n;j++){
                if(d[j]<0){
                    d[j]++;
                    ansx.push_back(j);
                    break;
                }
            }
        }
        while(d[i]<0){
            d[i]++;
            ansx.push_back(i);
            for(int j=1;j<=n;j++){
                if(d[j]>0){
                    d[j]--;
                    ansy.push_back(j);
                    break;
                }
            }
        }
    }
    cout<<ansx.size()<<'\n';
    for(int i=0;i<ansx.size();i++){
        cout<<ansy[i]<<" "<<ansx[i]<<'\n';
    }
    // puts(n==m?"Yes":"No");
}

int cnt[N][30];
void solve(){
    int n=read(),m=read();
    // string s[n+1]
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            cnt[j][s[j]-'a']++;
        }
    }
    for(int i=1;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            cnt[j][s[j]-'a']--;
        }
    }
    for(int i=0;i<m;i++){
        for(char j='a';j<='z';j++){
            if(cnt[i][j-'a'])cout<<j;
        }
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

map<int,int>ji,ou;
int a[N];
void solve(){
    int n=read();
    ji.clear();
    ou.clear();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i%2==1){
            ji[a[i]]++;
        }else ou[a[i]]++;
    }
    sort(a+1,a+1+n);
    int ans=1;
    for(int i=1;i<=n;i++){
        if(i%2==1){
            ji[a[i]]--;
            if(ji[a[i]]<0)ans=0;
        }else{
            ou[a[i]]--;
            if(ou[a[i]]<0)ans=0;
        }
    }
    puts(ans>0?"YES":"NO");
    
}

#define int long long
int fact[N],infact[N];
int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
void solve(){
    int n=read();
    string s;
    cin>>s;
    int m=0,nn=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1'&& s[i+1]=='1'){
            s[i]='2';
            s[i+1]='2';
            m++;
        }
        if(s[i]=='0') nn++;
    }
    cout<<fact[nn+m]*infact[m]%mod*infact[nn]%mod<<'\n';
}
signed main(){
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ){
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int t=read();
    while(t--){
        solve();
    }
}