Submission

Score: 20

User: navysrimuang

Problemset: ทางเชื่อม

Language: cpp

Time: 0.354 second

Submitted On: 2026-03-16 23:29:23

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

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<vector<ll>> dp(2,vector<ll>(n+2,0));
		vector<vector<bool>> blk(2,vector<bool>(n+2,0));
		for(int i = 0;i<2;i++){
			for(int j = 1;j<=n;j++){
				char c; 
				cin >> c;
				if(c == '#') blk[i][j] = 1;
			}
		}
		
		if(blk[0][1] && blk[1][1]){cout << 0 << "\n"; continue;}
		dp[0][1] = dp[1][1] = 2;
		if(blk[0][1]){
			dp[0][1] = 0;
			dp[1][1] = 1;
		}
		if(blk[1][1]){
			dp[1][1] = 0;
			dp[0][1] = 1;
		}
		
		for(int i = 2;i<=n;i++){
			if(!blk[0][i]) dp[0][i] = dp[0][i-1];
			if(!blk[1][i]) dp[1][i] = dp[1][i-1];
			if(!blk[0][i] && !blk[1][i]) dp[0][i] += dp[1][i-1];
			if(!blk[1][i] && !blk[0][i]) dp[1][i] += dp[0][i-1];
			dp[0][i] %= MOD;
			dp[1][i] %= MOD;
		}

//		for(int i = 0;i<2;i++){
//			for(int j = 1;j<=n;j++){
//				cout << dp[i][j] << " ";
//			}
//			cout << "\n";
//		}
		cout << (dp[0][n] + dp[1][n]) % MOD << "\n";
	}

	return 0;
}