Submission

Score: 100

User: kormuyang

Problemset: ทางเชื่อม

Language: cpp

Time: 0.514 second

Submitted On: 2025-12-15 12:56:42

#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();
}