1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define QCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr<<#x<<" "<<x<<endl
#define LL long long
using namespace std;
const int mod = 1e9+7;


int Newt[10010][10010];
int r1, r2, r3, wsp, roz, n, len, a, b, op, res;
string s1, s2, s3;
int sphere(int r){
	int ret = 0;
	for(int i=0;i<=r;i++){
		ret+=Newt[n][i];
		ret%=mod;
	}
	return ret;
}
int main(){
	QCK;
	cin>>n;
	cin>>r1>>s1>>r2>>s2>>r3>>s3;
	if(r1==r2&&s1==s2){
		swap(r2,r3);
		swap(s2,s3);	
	}
	if(r1>r2){
		swap(r1,r2);
		swap(s1,s2);	
	}
	bitset <10010> A, B;
	for(int i=0;i<s1.size();i++){
		if(s1[i]=='1')
			A[i]=1;
		if(s2[i]=='1')
			B[i]=1;
	}
	A^=B;
	roz=A.count();
	wsp=n-A.count();
	len=r1+r2-roz;
	Newt[0][0]=1;
	for(int i=1;i<=10000;i++){
		Newt[i][0]=1;
		for(int j=1;j<=i;j++){
			Newt[i][j]=(Newt[i-1][j]+Newt[i-1][j-1])%mod;		
		}
	}
	
	res=(sphere(r1)+sphere(r2))%mod;
	if(roz<=(abs(r1-r2)))
		res=sphere(r2);
	else if(roz>r1+r2);
	else{
		for(int i=r1-len;i<=r1;i++){
			if(i>roz)
				op=roz-i;
			else 
				op=i;
			if(op>=0)
				a=roz;
			else
			 	a=wsp;
			b=abs(i);
			res-=Newt[a][b];
			if(res<0)
				res+=mod;
		}
		
	}
	cout<<res<<endl;
	
}