Submission

Score: 100

User: navysrimuang

Problemset: ทางเชื่อม

Language: cpp

Time: 0.428 second

Submitted On: 2026-02-15 19:32:11

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

ll dp[3][5005];
char a[3][5005];

void solve(int n){
	for(int i = 1;i<=2;i++)
		for(int j = 1;j<=n;j++)
			cin >> a[i][j];
		
	for(int i = 1;i<=n;i++){
		if((a[1][i] == '#') && (a[2][i] == '#')){
			cout << "0\n";
			return;
		}
	}

	dp[1][0] = dp[2][0] = 1;
	
	for(int i = 1;i<=n;i++){

		if(a[1][i] == '.' && a[2][i] =='.'){
			dp[1][i] = (dp[1][i-1] + dp[2][i-1]) % MOD;
			dp[2][i] = dp[1][i];
		}else if(a[1][i] == '#' && a[2][i] == '.'){
			dp[1][i] = 0;
			dp[2][i] = dp[2][i-1];
		}else if(a[1][i] == '.' && a[2][i] == '#'){
			dp[2][i] = 0;
			dp[1][i] = dp[1][i-1];
		}
	}
	cout << (dp[1][n] + dp[2][n]) % MOD << "\n";
}
int main(){

	cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		solve(n);
	}
	return 0;
}