Submission

PPPPPPPPPP

Score: 100

User: MiyaZaki1072

Problemset: ทางเชื่อม

Language: cpp

Time: 0.556 second

Submitted On: 2025-04-25 16:00:01

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MD = 1e9 + 7;
ll dp[5][5020];
char a[5][5010];
void solve() {
    int n;cin >> n;
    int ch = 0;
    for (int i=1;i<= 2;i++) {
        for(int j=1;j<=n;j++)cin>>a[i][j];
    }
    for(int i=1;i<=n;i++){
        if(a[1][i] == a[2][i] && a[1][i] == '#'){
            cout<<"0\n";
            return;
        }
    }
    dp[1][0] = dp[2][0] = 1;
    for (int i = 1; i <= n; ++i) {
        if (a[1][i] == '.' && a[2][i] == '.') {
            dp[1][i] = (dp[1][i-1] + dp[2][i-1]) % MD;
            dp[2][i] = dp[1][i];
        }
        else if (a[1][i] == '#' && a[2][i] == '.') {
            dp[1][i] = 0;
            dp[2][i] = dp[2][i - 1];
        }
        else if (a[1][i] == '.' && a[2][i] == '#') {
            dp[1][i] = dp[1][i - 1];
            dp[2][i] = 0;
        }
    }
    cout<<(dp[1][n] + dp[2][n])%MD<<"\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc;cin>>tc;
    while(tc--)solve();
}