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
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)
#define MAX(dst,src) dst = max(dst, (src))
#define MIN(dst,src) dst = min(dst, (src))

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MOD = 1000000007;
LL powe(LL a, LL b) {
  LL result = 1;
  while (b) {
    if (b&1) (result *= a) %= MOD;
    (a *= a) %= MOD;
    b >>= 1;
  }
  return result;
}

LL inv(LL a) {
  return powe(a, MOD-2);
}

LL fact[11111];
LL invfact[11111];

LL DP[11111][11111];

int R[3];
char B[3][11111];
int C[4];

LL SN(int N, int K) {
  return fact[N] * invfact[K] % MOD * invfact[N-K] % MOD;
}
LL SNC[4][11111];

int main() {
  fact[0] = 1;
  FOR(i,1,11111) fact[i] = fact[i-1] * i % MOD;
  REP(i,11111) invfact[i] = inv(fact[i]);

  int N;
  scanf("%d", &N);
  REP(i,3) {
    scanf("%d%s", &R[i], B[i]);
    R[i] = N-1 - R[i];
  }
  REP(i,N) {
    int m = (B[0][i]-'0') + ((B[1][i]-'0')<<1) + ((B[2][i]-'0')<<2);
    if (m&4) m ^= 7;
    ++C[m];
  }

  REP(i,4)REP(j,C[i]+1) SNC[i][j] = SN(C[i],j);

  REP(a,C[0]+1)REP(b,C[3]+1) {
    int r2 = a + b;
    int r1 = a + C[3] - b;
    DP[r2][r1] = SNC[0][a] * SNC[3][b] % MOD;
  }

  int K = C[0] + C[3];
  REP(i,K+1)REP(j,K) DP[i][j+1] += DP[i][j];
  REP(j,K+1) DP[0][j] %= MOD;
  REP(i,K)REP(j,K+1) (DP[i+1][j] += DP[i][j]) %= MOD;

  LL result = 0;
  REP(a,C[1]+1)REP(b,C[2]+1) {
    int l = min(
      R[0]-(C[1]-a)-b,
      R[1]-a-(C[2]-b)
    );
    int k = R[2] - a - b;
    if (k < 0 || l < 0) continue;

    result += SNC[1][a] * SNC[2][b] % MOD * DP[min(k,K)][min(l,K)] % MOD;
  }
  result = powe(2,N) - result;
  result %= MOD;
  result += MOD;
  result %= MOD;
  printf("%d\n", (int)result);
}