Submission

Score: 0

User: anak

Problemset: ทางเชื่อม

Language: cpp

Time: 1.097 second

Submitted On: 2026-04-01 03:58:08

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()

const int mod = 1e9+7;
void tc() {
    int n;
    cin >> n;
    vector<vector<char>> grid(3,vector<char>(n+1));
    vector<vector<vector<int>>> dp(3,vector<vector<int>>(n+1,vector<int>(6,0)));
    for(int i=1;i<=2;i++) {
        for(int j=1;j<=n;j++) {
            cin >> grid[i][j];
            if(grid[i][j] == '#') {
                for(int k=1;k<=5;k++) {
                    dp[i][j][k] = 0;
                }
            }
        }
    }
    for(int i=1;i<=2;i++) {
        for(int k=1;k<=5;k++) {
            dp[i][1][k] = 1;
        }
    }
    dp[1][1][2] = 0;dp[1][1][3] = 0;dp[1][1][4] = 0; dp[2][1][2] = 0;dp[2][1][3] = 0;dp[2][1][5] = 0;
    function<int(int,int)> f = [&](int i,int j) {
        if(i == 1) return (dp[i][j][1]%mod + dp[i][j][5]%mod)%mod;
        else return (dp[i][j][1]%mod + dp[i][j][4]%mod)%mod;
    };
    for(int j=2;j<=n;j++) {
        if(grid[1][j] != '#') dp[1][j][3] = (dp[1][j][3]%mod + f(1,j-1)%mod)%mod;
        if(grid[2][j] != '#') dp[2][j][2] = (dp[2][j][2]%mod + f(2,j-1)%mod)%mod;

        if(grid[1][j] != '#') {
            dp[1][j][1] = (dp[1][j][1]%mod + f(1,j-1)%mod)%mod;
            dp[1][j][5] = (dp[1][j][5]%mod + dp[2][j][2]%mod)%mod;
        }
        if(grid[2][j] != '#') {
            dp[2][j][1] = (dp[2][j][1]%mod + f(2,j-1)%mod)%mod;
            dp[2][j][4] = (dp[2][j][4]%mod + dp[1][j][3]%mod)%mod;
        }
    }
    cout << (f(1,n)%mod + f(2,n)%mod)%mod << '\n';

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