void solve(){
    int n=read(),m=read();
    string s,t;
    cin>>s>>t;
    int ans=1;
    for(int i=0;i<s.size()-1;i++){
        if(s[i]==s[i+1]){
            int len=s.size();
            for(int j=len-1;j>=i+1;j--){
                t+=s[j];
            }
            s.erase(s.begin()+i+1,s.end());
            break;
        }
    }
    for(int i=0;i<t.size()-1;i++){
        if(t[i]==t[i+1]){
            int len=t.size();
            for(int j=len-1;j>=i+1;j--){
                s+=t[j];
            }
            t.erase(t.begin()+i+1,t.end());
            break;
        }
    }
    for(int i=0;i<s.size()-1;i++){
        if(s[i]==s[i+1])ans=0;
    }
    for(int i=0;i<t.size()-1;i++){
        if(t[i]==t[i+1])ans=0;
    }
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

int a[55];
void solve(){
    int n=read(),k=read(),ans=1;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        if(x<=k&&k<=y){
            for(int j=x;j<=y;j++){
                a[j]++;
            }
        }
    }
    for(int i=1;i<=50;i++){
        if(i!=k&&a[i]>=a[k]){
            ans=0;
            break;
        }
    }
    
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

int a[N],b[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    multiset<int>se;
    int hd=0;
    for(int i=1;i<=n;i++){
        se.insert(a[i]-hd);
        int ans=0;
        while(se.size()&&*se.begin()+hd<=b[i]){
            ans+=*se.begin()+hd;
            se.erase(se.begin());
        }
        ans+=se.size()*b[i];
        hd-=b[i];
        cout<<ans<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

int fact[N],infact[N];

int qmi(int a, int k, int p){  
    int res = 1;
    while (k){
        if (k & 1) res =res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void solve(){
    int n=read(),ans=1;
    for(int i=1;i<=n/3;i++){
        int a[4];
        a[1]=read(),a[2]=read(),a[3]=read();
        sort(a+1,a+1+3);
        if(a[1]==a[2]&&a[2]==a[3]){
            (ans*=3)%=mod;
        }else if(a[3]==a[2]){
            ans=ans;
        }else if(a[2]==a[1]){
            (ans*=2)%mod;
        }else ans=ans;
        ans%=mod;
    }
    cout<<ans*fact[n/3]%mod*infact[n/6]%mod*infact[n/6]%mod<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t=1;
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;
}
    while(t--){
        solve();
    }
}