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
79
80
81
82
83
#include <bits/stdc++.h>
#define fi first
#define sc second
#define mp make_pair
#define pb push_back
#define forn(I,P,K) for(int (I)=(P);(I)<=(K);++(I))
using namespace std;
const int P=1000000007;
const int MM=10013;
typedef long long ll;
bitset<10000> A,B,C;
bitset<20> x,y,z,t;
inline int add(const int &x, const int &y){return (x+y>=P?x+y-P:x+y);}
inline int mul(const int &x, const int &y){return 1LL*x*y%P;}
int inv[MM],preD[MM],preN[MM],Apo[MM],Bpo[MM],Cpo[MM],Dpo[MM];
inline void Init(int a, int b, int c, int d, int n)
{
    inv[1]=1;
    forn(i,2,n) inv[i]=P-mul(inv[P%i],(P/i));
    Apo[0]=1;Bpo[0]=1;Cpo[0]=1;Dpo[0]=1;preD[0]=1;
    forn(i,1,a) Apo[i]=mul(Apo[i-1],mul(a-i+1,inv[i]));
    forn(i,1,b) Bpo[i]=mul(Bpo[i-1],mul(b-i+1,inv[i]));
    forn(i,1,c) Cpo[i]=mul(Cpo[i-1],mul(c-i+1,inv[i]));
    forn(i,1,d) Dpo[i]=mul(Dpo[i-1],mul(d-i+1,inv[i])),preD[i]=add(Dpo[i],preD[i-1]);
    int x=1;preN[0]=1;
    forn(i,1,n) x=mul(x,mul(n-i+1,inv[i])),preN[i]=add(x,preN[i-1]);
}
inline int pref(int x)
{
    if(x<0) return 0;
    else    return preD[x];
}
int main()
{
    ios_base::sync_with_stdio(0);
    int n,R1,R2,R3;
    int a=0,b=0,c=0,d=0;
    ll wyn=0;
    cin>>n;
    cin>>R1>>A>>R2>>B>>R3>>C;
    B^=A;
    C^=A;
    A^=A;
    forn(i,0,n-1)
    {
        if(B[i]&&C[i])   a++;
        if(B[i]&&(!C[i]))b++;
        if((!B[i])&&C[i])c++;
        if(!(B[i]||C[i]))d++;
    }
    Init(a,b,c,d,n);
    if(A==B)
    {
        R1=max(R1,R2);
        wyn=add(preN[R1],preN[R3]);
        int x=0;
        forn(i,0,c) x=add(x,mul(Cpo[i],pref(min(R1-i,min(R3-c+i,d)))));
        return cout<<(wyn-x>=0?wyn-x:wyn-x+P),0;
    }
    if(B==C)
    {
        R2=max(R2,R3);
        wyn=add(preN[R1],preN[R2]);
        int x=0;
        forn(i,0,a) x=add(x,mul(Apo[i],pref(min(R1-i,min(R2-a+i,d)))));
        return cout<<(wyn-x>=0?wyn-x:wyn-x+P),0;
    }
    if(A==C)
    {
        R1=max(R1,R3);
        wyn=add(preN[R2],preN[R1]);
        int x=0;
        forn(i,0,b) x=add(x,mul(Bpo[i],pref(min(R1-i,min(R2-b+i,d)))));
        return cout<<(wyn-x>=0?wyn-x:wyn-x+P),0;
    }
    forn(i,0,n-1)   x[i]=A[i],y[i]=B[i],z[i]=C[i];
    forn(i,0,(1<<n)-1)
    {
        t=i;
        if((x^t).count()<=R1||(y^t).count()<=R2||(z^t).count()<=R3) wyn++;
    }
    return cout<<wyn,0;
}