Submission

Score: 0

User: C12

Problemset: ทางเชื่อม

Language: cpp

Time: 0.314 second

Submitted On: 2026-01-08 01:16:41

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

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define tiiii tuple<ll,ll,ll,ll>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define mt make_tuple
 
#define mpiiii(a,b,c) make_pair(a,make_pair(b,c));
ll mod = 1000000007LL;

ll n;
bool board[2][5001];
ll prevs[2],curr[2];

void solve(){
    cin >> n;
    char t;

    for(int i = 0;i < n;i++){
        cin >> t;
        // if(t == '\n') continue;

        if(t == '.'){
            board[0][i] = 1;
        }
        else{
            board[0][i] = 0;
        }
    }

    for(int i = 0;i < n;i++){
        cin >> t;
        // if(t == '\n') continue;

        if(t == '.'){
            board[1][i] = 1;
        }
        else{
            board[1][i] = 0;
        }
    }

    prevs[0] = 1;
    prevs[1] = 1;
    for(int i = 0;i < n;i++){
        curr[0] = 0;
        curr[1] = 0;

        if(board[0][i]){
            curr[0] += prevs[0];
        }
        if(board[1][i])
        {
            curr[1] += prevs[1];
        }
        if(board[0][i] && board[1][i]){
            curr[0] += prevs[1];
            curr[1] += prevs[0];
        }

        while(curr[0] >= mod){
            curr[0] -= mod;
        }
        while(curr[1] >= mod){
            curr[1] -= mod;
        }
        prevs[0] = curr[0];
        prevs[1] = curr[1];
    }

    // cout << (curr[0] + curr[1]) << '\n';
    ll num = 2;
    for(int i = 0;i < n;i++) num *= 2LL;
    cout << num << '\n';

    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
 
    cin >> q;

    while(q--)
        solve(); 

    return 0;
}
/*
3
1
.
.
2
..
..
2
.#
..

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

4
8
........
........
9
.........
.........
10
..........
..........
20
....................
....................

*/