Submission

Score: 20

User: krittaphot

Problemset: ทางเชื่อม

Language: cpp

Time: 0.304 second

Submitted On: 2026-03-04 14:28:34

#include <bits/stdc++.h>

using namespace std;
int dp[2][5001];
bool mp[2][5001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	long long q;
	cin >> q;
	while(q--){
		long long n;
		cin >> n;
		dp[0][0] = 1;
		dp[1][0] = 1;
		for(long long i = 0;i<2;i++){
			for(long long j = 1;j<n+1;j++){
				char c;
				cin >> c;
				if(c == '#'){
					mp[i][j] = true;
				}
			}
		}
//		
//		for(long long i = 0;i<2;i++){
//			for(long long j = 0;j<n+1;j++){
//				cout << mp[i][j] << " ";
//			}
//			cout << "\n";
//		}
	
		for(long long j = 1;j<n+1;j++){
			for(long long i = 0;i<2;i++){
				if(mp[i][j]){
					dp[i][j] = 0;
					continue;
				}
				else if(i == 0){
					if(mp[i+1][j]){
						dp[i][j] = (dp[i][j-1] % 1000000007);
					}
					else{
						dp[i][j] = (dp[i][j-1] + dp[i+1][j-1])% 1000000007 ;
					}
				}
				else{
					if(mp[i-1][j]){
						dp[i][j] = (dp[i][j-1] % 1000000007) ;
					}
					else{
						dp[i][j] = (dp[i][j-1] + dp[i-1][j-1])% 1000000007 ;
					}
				}
			}
		}
		
//		cout << dp[0][n] << " " << dp[1][n] << "\n";
		cout << (dp[0][n]+dp[1][n])  % 1000000007 << "\n";
	}
}