Submission

Score: 0

User: wtpza

Problemset: ทางเชื่อม

Language: cpp

Time: 0.149 second

Submitted On: 2026-03-13 19:54:51

#include<bits/stdc++.h>
using namespace std;

int main(){
    const int MOD = 100000007;
    cin.tie(0)->sync_with_stdio(0);
    const int direcy[]={0,1,-1};
    const int direcx[]={1,0,0};
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        int a;
        cin >> a;
        vector<string> wow(2);
        wow[0].push_back('?');
        wow[1].push_back('?');
        string jj, kk;
        cin >> jj >> kk;
        wow[0] += jj;
        wow[1] += kk;
        wow[0].push_back('?');
        wow[1].push_back('?');
        vector<vector<int>> dp(2, vector<int>(a + 2, 0));
        dp[0][0] = 1;
        dp[1][0] = 1;
        for(int x = 1 ; x < a + 2 ; x++){
            if(wow[0][x] != '#'){
                dp[0][x] = (dp[0][x] + dp[0][x-1]) % MOD;
                if(wow[1][x] != '#'){
                    dp[0][x] = (dp[0][x] + dp[1][x-1]) % MOD;
                }
            }
            if(wow[1][x] != '#'){
                dp[1][x] = (dp[1][x] + dp[1][x-1]) % MOD;
                
                if(wow[0][x] != '#'){
                    dp[1][x] = (dp[1][x] + dp[0][x-1]) % MOD;
                }
            }
        }
        
        int ans = (dp[0][a+1]/2 + dp[1][a+1]/2) % MOD;
        cout << ans << "\n";
    }
}