Submission

Score: 20

User: kavin8888

Problemset: ทางเชื่อม

Language: cpp

Time: 0.391 second

Submitted On: 2026-03-05 20:02:24

#include<bits/stdc++.h>
using namespace std; 
#define int long long
const int MAX_N=5054;
const int MOD=1e9+7;
int t;
vector<vector<int>> dp;
vector<vector<char>> a;
void solve() {
	int n; cin>>n;
	a.assign(5,vector<char>(MAX_N+5));
	dp.assign(5,vector<int>(MAX_N+5));
	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[2][i]=(dp[2][i-1])%MOD,dp[1][i]=0;
		else if(a[2][i]=='#' && a[1][i]=='.') dp[1][i]=(dp[1][i-1])%MOD,dp[2][i]=0;
		else if(a[1][i]=='.' && a[2][i]=='.') {
			dp[1][i]=(dp[1][i-1]+dp[2][i-1])%MOD;
			dp[2][i]=(dp[2][i-1]+dp[1][i-1])%MOD;
		} 
	}
	cout<<(dp[1][n]+dp[2][n])%MOD<<'\n';
	return;
}
signed main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}