Submission

Score: 20

User: C12

Problemset: ทางเชื่อม

Language: cpp

Time: 0.111 second

Submitted On: 2026-01-08 11:02:58

#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 = 1e9+7;

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

void solve(){
    cin >> n;
    char t[5001];
    
    cin >> t;
    for(int i = 0;i < n;i++){
        // cin >> t;
        // if(t == '\n') continue;

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

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

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

    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] % mod;
        prevs[1] = curr[1] % mod;
    }
    ll out = (curr[0] + curr[1]) % mod;
    cout << out << endl;
    // 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
....................
....................

7
40
........................................
........................................
42
.....................#....................
..........................................
29
.............................
.............................
31
...................#...........
...............................
21
.....................
.....................
30
##...................##.......
............................##
80
.........................................#######################################
................................................................................


2,147,483,648
1,000,000,007
30
147,483,634
29
73,741,817

23240159
23240159
73741817
73741817
4194304
4194304
23240159
*/