T1 (40pts-100pts)

# include<iostream>
# include<string>
# include<cmath>
# include<cstdio>
using namespace std;

const int N=1e5+2;
int t,n,a[N],b[N],c[N],d[N],ans,tmp;
string s1,s2,t1,t2;

void solve(){
	cin>>n>>s1>>s2>>t1>>t2;
	ans=a[n]=b[n]=c[n]=d[n]=0;
	for(int i=n-1;i>=0;--i){
		if(s1[i]=='0'){
			a[i]=a[i+1]*(t1[i]-'0')*(t1[i+1]-'0')+1;
			b[i]=b[i+1]*(t1[i]-'0')*(t1[i+1]-'0');
		}
		else{
			a[i]=a[i+1]*(t1[i]-'0')*(t1[i+1]-'0');
			b[i]=b[i+1]*(t1[i]-'0')*(t1[i+1]-'0')+1;
		}
		if(s2[i]=='0'){
			c[i]=c[i+1]*(t2[i]-'0')*(t2[i+1]-'0')+1;
			d[i]=d[i+1]*(t2[i]-'0')*(t2[i+1]-'0');
		}
		else{
			c[i]=c[i+1]*(t2[i]-'0')*(t2[i+1]-'0');
			d[i]=d[i+1]*(t2[i]-'0')*(t2[i+1]-'0')+1;
		}
	}
	int i=0;
	while(i<n){
		if(a[i]+b[i]==c[i]+d[i]){
			ans+=a[i]+b[i]-abs(a[i]-c[i]);
			i+=a[i]+b[i];
		}
		else if(a[i]+b[i]>c[i]+d[i]){
			tmp=i+c[i]+d[i];
			if(a[i]>=c[i]&&b[i]>=d[i]){
				ans+=c[i]+d[i];
				a[tmp]=a[i]-c[i];
				b[tmp]=b[i]-d[i];
			}
			else if(a[i]>=c[i]){
				ans+=c[i]+b[i];
				a[tmp]=a[i]-(c[i]+d[i]-b[i]);
				b[tmp]=0;
			}
			else if(b[i]>=d[i]){
				ans+=a[i]+d[i];
				b[tmp]=b[i]-(d[i]+c[i]-a[i]);
				a[tmp]=0;
			}
			i=tmp;
		}
		else{
			tmp=i+a[i]+b[i];
			if(c[i]>=a[i]&&d[i]>=b[i]){
				ans+=a[i]+b[i];
				c[tmp]=c[i]-a[i];
				d[tmp]=d[i]-b[i];
			}
			else if(c[i]>=a[i]){
				ans+=a[i]+d[i];
				c[tmp]=c[i]-(a[i]+b[i]-d[i]);
				d[tmp]=0;
			}
			else if(d[i]>=b[i]){
				ans+=c[i]+b[i];
				d[tmp]=d[i]-(b[i]+a[i]-c[i]);
				c[tmp]=0;
			}
			i=tmp;
		}
	}
	cout<<ans<<endl;
}

int main(){
	freopen("edit2.in","r",stdin);
	freopen("edit.out","w",stdout);
	cin>>t;
	while(t--) solve();
	return 0;
}

T2 (100pts)

# include<iostream>
# include<algorithm>
using namespace std;
# define ll long long

const int M=1e5+2;
const ll mod=1e9+7;

struct limit{
	int c;
	ll d;
	void in(){
		cin>>c>>d;
	}
}a[M];

int t,n,m,g;
ll v,tmp,ans;

bool cmp(limit x,limit y){
	return (x.c==y.c?x.d<y.d:x.c<y.c);
}

ll pow(ll x,int y){
	if(x==0||x==1||y==1) return x;
	if(y==0) return 1;
	ll t=pow(x,y/2);
	if(y%2) return t*t%mod*x%mod;
	else return t*t%mod;
}

void solve(){
	cin>>n>>m>>v;
	ans=1; //务必记得初始化 
	for(int i=1;i<=m;++i) a[i].in();
	sort(a+1,a+m+1,cmp); //c_j不一定按升序给出 
	for(int i=0;i<=m;++i){
		if(i>0&&i<m&&a[i].c==a[i+1].c){
			if(a[i].d==a[i+1].d) continue;
			else{
				ans=-1;
				break;
			}
		} //如果有矛盾的一元限制（如样例1-3），那么结果为0，务必记得特判 
		if(i==0){
			g=a[1].c-1;
			tmp=pow(v%mod,2*g);
		}
		else if(i==m){
			g=n-a[m].c;
			tmp=pow(v%mod,2*g);
		}
		else{
			g=a[i+1].c-a[i].c;
			tmp=(pow(v%mod,2*g)-pow(v%mod,g-1)*(v-1)%mod+mod)%mod;
		}
		ans=ans*tmp%mod;
	}
	if(ans==-1) cout<<0<<endl;
	else cout<<ans%mod<<endl;
}

int main(){
	cin>>t;
	while(t--) solve();
	return 0;
}