Submission

Score: 100

User: mantaggez

Problemset: ทางเชื่อม

Language: cpp

Time: 0.461 second

Submitted On: 2026-03-20 15:47:35

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll nx = 5e3+5;
const ll MOD = 1e9+7;

ll n, l;
ll dp[3][nx][6];
char grid[3][nx];

void solve()
{
    cin >> l;
    for(ll i=1;i<=2;i++)
        for(ll j=1;j<=l;j++)
            cin >> grid[i][j];

    memset(dp, 0, sizeof(dp));

    if(grid[1][1] == '.')
        dp[1][1][1] = dp[1][1][3] = 1;
    if(grid[2][1] == '.')
    dp[2][1][1] = dp[2][1][2] = 1;
    
    for(ll j=1;j<=l;j++) {
        // i = 1
        if(grid[1][j] == '.') {
            dp[1][j][1] += (dp[1][j - 1][1] + dp[1][j - 1][5]) % MOD;
            dp[1][j][3] += (dp[1][j - 1][1] + dp[1][j - 1][5]) % MOD;
        }
        
        // i = 2
        if(grid[2][j] == '.') {
            dp[2][j][1] += (dp[2][j - 1][1] + dp[2][j - 1][4]) % MOD;
            dp[2][j][2] += (dp[2][j - 1][1] + dp[2][j - 1][4]) % MOD;
        }
        
        // special
        if(grid[1][j] == '.')
            dp[1][j][5] += dp[2][j][2] % MOD;

        if(grid[2][j] == '.')
            dp[2][j][4] += dp[1][j][3] % MOD;
    }

    // cout << dp[1][l][1] << ' ' <<  dp[1][l][5] << ' ' << dp[2][l][1] << ' ' << dp[2][l][4] << '\n';
    
    ll ans = (dp[1][l][1] + dp[1][l][5]) % MOD + (dp[2][l][1] + dp[2][l][4]) % MOD;
    cout << ans % MOD << '\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    while(n--) {
        solve();
    }

    return 0;
}