Submission

Score: 20

User: navysrimuang

Problemset: ทางเชื่อม

Language: cpp

Time: 0.453 second

Submitted On: 2026-03-17 00:45:20

#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]) dp[0][1] = 1;	
		if(!blk[1][1]) dp[1][1] = 1;	
		
		if(!blk[0][1] && !blk[1][1]){
			dp[0][1] = 2;
			dp[1][1] = 2;
		}
		for(int i = 2;i<=n;i++){
			if(!blk[0][i]){
				dp[0][i] = (dp[0][i-1] % MOD);
				if(!blk[1][i]) dp[0][i] = ((dp[0][i] + dp[1][i-1])%MOD);
			}
			
			if(!blk[1][i]){
				dp[1][i] = (dp[1][i-1]%MOD);
				if(!blk[0][i]) dp[1][i] = ((dp[1][i]+dp[0][i-1])%MOD);
			}
				
			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;
}