Submission

Score: 0

User: Nathako9n

Problemset: ทางเชื่อม

Language: cpp

Time: 1.092 second

Submitted On: 2026-01-18 14:45:52

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;

const ll mod = 1000000007;
string ar[2];
int n, m;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> m;
    while(m--){
        cin >> n;
        cin >> ar[0] >> ar[1];

        vector<vector<vector<ll>>> dp(2,vector<vector<ll>>(n+2, vector<ll>(n+2, -1)));

        vector<vector<vector<bool>>> vis(2,vector<vector<bool>>(n,vector<bool>(n, false)));


        function<ll(int,int,int)> sol = [&](int i, int j,int k){
            if(j == n) return 1LL;
            if(dp[i][j][k] != -1) return dp[i][j][k];
            if(vis[i][j][k]) return dp[i][j][k];
            vis[i][j][k] = true;
            ll s1 = 0;
            if(ar[i][j+1] != '#')
                s1 = (s1 + sol(i, j+1,0)) % mod;

            if(k==0&&i == 0 && ar[1][j] != '#')
                s1 = (s1 + sol(1, j,1)) % mod;

            if(k==0&&i == 1 && ar[0][j] != '#')
                s1 = (s1 + sol(0, j,1)) % mod;
            return dp[i][j][k] = s1;
        };

        cout << sol(0,0,0)+sol(1,0,0) << endl;


    }
    return 0;
}


/*

3
1
.
.
2
..
..
2
.#
..

1
1
.
.


*/