Submission

Score: 20

User: devilpoohs

Problemset: ทางเชื่อม

Language: cpp

Time: 0.562 second

Submitted On: 2025-10-23 12:50:59

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define int long long
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]%mod);
    int cnt=0;
    if(ar[0][j-1]==true){
        cnt+=think(0,j-1,ar,dp);
        cnt%=mod;
    }
        

    if(ar[1][j-1]==true){
        cnt+=think(1,j-1,ar,dp);
        cnt%=mod;
    }

    dp[i][j]=(cnt%mod);
    return cnt%mod;
}

void solve(){
    int l;
    cin>>l;
    vector<vector<bool>> ar(2,vector<bool>(l+1,1));
    char ch;
    for(int j=0;j<l;j++){
        cin>>ch;
        if(ch=='#'){
            ar[0][j]=0;
            ar[0][j+1]=0;
        }
    }
    for(int j=0;j<l;j++){
        cin>>ch;
        if(ch=='#'){
            ar[1][j]=0;
            ar[1][j+1]=0;
        }
    }
    vector<vector<int>> dp(2,vector<int>(l+1,-1));
    int ans=0;
    if(ar[0][l]==true){
        ans+=think(0,l,ar,dp);
        ans%=mod;
    }
    if(ar[1][l]==true){
        ans+=think(1,l,ar,dp);
        ans%=mod;
    }
    cout<<ans%mod<<'\n';

}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    while(n--){
        solve();
    }
    return 0;
}
/*
3 
1 
. 
. 
2 
.. 
.. 
2 
.# 
..
*/