Submission

Score: 20

User: devilpoohs

Problemset: ทางเชื่อม

Language: cpp

Time: 0.645 second

Submitted On: 2025-09-21 16:28:41

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n;
int think(int i,int j,vector<vector<bool>>& ar,vector<vector<int>>& dp){
    if(j==0){
        return 1;
    }
    if(dp[i][j]!=-1) return dp[i][j];
    int cnt=0;
    if(j==n+1){
        if(ar[0][n]==true){
            cnt+=think(0,n,ar,dp);
        }
        if(ar[1][n]==true){
            cnt+=think(1,n,ar,dp);
        }
    }else if(i==0){
        if(ar[0][j-1]==true){
            cnt+=think(0,j-1,ar,dp);
        }
        if(ar[1][j-1]==true){
            cnt+=think(1,j-1,ar,dp);
        }
    }
    if(i==1){
        if(ar[0][j-1]==true) {
            cnt+=think(0,j-1,ar,dp);
        }
        if(ar[1][j-1]==true){
            cnt+=think(1,j-1,ar,dp);
        }
    }
    
    return dp[i][j]=cnt%mod;
}

void solve(){
    cin>>n;
    vector<vector<bool>> ar(2,vector<bool>(n+1));
    char ch;
    for(int i=1;i<=n;i++){
        cin>>ch;
        if(ch=='#') ar[0][i-1]=ar[0][i]=false;
        else ar[0][i-1]=ar[0][i]=true;
    }
    for(int i=1;i<=n;i++){
        cin>>ch;
        if(ch=='#') ar[1][i-1]=ar[1][i]=false;
        else ar[1][i-1]=ar[1][i]=true;
    }
    // for(int i=0;i<2;i++){
    //     for(int j=0;j<=n;j++){
    //         if(ar[i][j]) cout<<'Y';
    //         else cout<<'N';
    //     }
    //     cout<<'\n';
    // }
    vector<vector<int>> dp(2,vector<int>(n+2,-1));
    cout<<think(0,n+1,ar,dp)<<'\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    cin>>q;
    while(q--){
        solve();
    }
    // cout<<mod;
    return 0;
}
/*
3 
1 
#
. 
2 
.#
.#
3
.#. 
..#

3 
1 
. 
. 
2 
.. 
.. 
2 
.# 
..
*/