Submission

Score: 30

User: kormuyang

Problemset: ทางเชื่อม

Language: cpp

Time: 0.156 second

Submitted On: 2025-12-16 01:40:06

#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;
    vector<string> a(3);
    cin >> a[1] >> a[2];
    a[1] = ' ' + a[1];
    a[2] = ' ' + a[2];
    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();
}