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
75
76
77
78
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
int n;
int r[4];
bitset<10010> tab[4];
int own[4];
int choose[10010][10010];
int pref[10010][10010];
long long pom[10010];
long long wyn1(int t)
{
	int i;
	long long w=0;
	for(i=0;i<=r[t];i++)
		w=(w+(long long)choose[n][i])%mod;
	return w;
}
long long wyn2(int t1,int t2)
{
	long long w=0;
	int b,i;
	b=(tab[t1]&(~tab[t2])).count()+(tab[t2]&(~tab[t1])).count();
	pom[0]=(long long)choose[n-b][0];
	for(i=1;i<=n;i++)
		pom[i]=(pom[i-1]+(long long)choose[n-b][i])%mod;
	for(i=max(0,b-r[t2]);i<=min(b,r[t1]);i++)
		w=(pom[min(r[t1]-i,r[t2]+i-b)]*(long long)choose[b][i]+w)%mod;
	return w;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int none,x,y;
	long long wyn=0,w;
	cin>>n;
	for(int j:{1,2,3})
		cin>>r[j]>>tab[j];
	own[1]=((tab[1])&(~tab[2])&(~tab[3])).count();
	own[2]=((~tab[1])&(tab[2])&(~tab[3])).count();
	own[3]=((~tab[1])&(~tab[2])&(tab[3])).count();
	own[1]+=((~tab[1])&(tab[2])&(tab[3])).count();
	own[2]+=((tab[1])&(~tab[2])&(tab[3])).count();
	own[3]+=((tab[1])&(tab[2])&(~tab[3])).count();
	none=n-own[1]-own[2]-own[3];
	for(x=0;x<=n;x++)
	{
		choose[x][0]=1;
		for(y=1;y<=x;y++)
			choose[x][y]=((long long)choose[x-1][y]+(long long)choose[x-1][y-1])%mod;
	}
	for(x=0;x<=none;x++)
	{
		for(y=0;y<=own[3];y++)
			pref[x+y+1][x+own[3]-y+1]=((long long)choose[none][x]*(long long)choose[own[3]][y]+(long long)pref[x+y+1][x+own[3]-y+1])%mod;
	}
	for(x=1;x<=none+own[3]+1;x++)
	{
		for(y=1;y<=none+own[3]+1;y++)
			pref[x][y]=((((long long)pref[x][y]+(long long)pref[x][y-1])%mod+(long long)pref[x-1][y])%mod-(long long)pref[x-1][y-1])%mod;
	}
	for(x=max(0,own[1]-min(r[2],r[3]));x<=min(own[1],r[1]);x++)
	{
		w=0;
		for(y=max(0,max(x+own[2]-r[1],own[1]-x+own[2]-r[3]));y<=min(own[2],r[2]-own[1]+x);y++)
			w=((long long)choose[own[2]][y]*(long long)pref[min(none+own[3],r[3]+x+y-own[1]-own[2])+1][min(none+own[3],min(r[1]+y-x-own[2],r[2]+x-y-own[1]))+1]+w)%mod;
		wyn=(w*(long long)choose[own[1]][x]+wyn)%mod;
	}
	//cerr<<wyn1(1)<<" "<<wyn1(2)<<" "<<wyn1(3)<<" "<<wyn2(1,2)<<" "<<wyn2(1,3)<<" "<<wyn2(2,3)<<"\n";
	wyn+=wyn1(1)+wyn1(2)+wyn1(3)-wyn2(1,2)-wyn2(1,3)-wyn2(2,3);
	cout<<((wyn%mod)+mod)%mod<<"\n";
	return 0;
}