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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#include <cstdio>
#include <algorithm>
#include <cmath>
//#include <cassert>
using namespace std;

long const MAXN = 10001;
long P = 1000000007;
long n;
long r[3];
long dists[3][3];
long x[3][MAXN];
long BC[MAXN][MAXN];

long modmult(long x, long y) {
  return ((long long) x)*y % P;
}

long modmult(long x, long y, long z) {
  return modmult(modmult(x, y), z);
}

// binomial coefficient nCk modulo MOD
long bc(long n, long k) {
  return BC[n][k];
}

void read() {
  char c;
  scanf("%ld\n", &n);
  for(int i=0; i<3; i++) {
    scanf("%ld ", &r[i]);
    for (int j=0; j<n; j++) {
      scanf("%c", &c);
      if (c == '0') {
        x[i][j] = 0;
      } else {
        x[i][j] = 1;
      }
    }
  }
  for (int i=0; i<3; i++) {
    dists[i][i] = 0;
    for (int j=i+1; j<3; j++) {
      long d = 0;
      for (int k=0; k<n; k++) {
        if (x[i][k] != x[j][k]) {
          d ++;
        }
      }
      dists[i][j] = d;
      dists[j][i] = d;
    }
  }
}

long solve1(int index) {
    long result = 0;
    for (long i=0; i<=r[index]; i++) {
        result = (result + bc(n, i)) % P;
    }
//    printf("solve1(%ld)=%ld\n", index, result);
    return result;
}

long solve1_ecluding(int index1, int index2) {
  //  printf("solve1_ecluding\n");
    long result = 0;
    long d = dists[index1][index2];
  //  printf("debug: %ld %ld %ld\n", r1, r2, d);
    long kmin = max((long) 0, r[index2] - d + 1);
    for(long k=kmin; k<=min(r[index1], n-d); k++) {
        long innersum = 0;
        long b1 = k + d - r[index1];
        long b2 = r[index2] - k + 1;
        long imin = max(max((long) 0, b1), b2);
  //      printf("debug_k: %ld %ld %ld\n", k, x, y);
        for (long i=imin; i<=d; i++) {
          innersum = (innersum + bc(d, i)) % P;
        }
    //    printf("debug_k_innersum: %ld\n", innersum);
        long innermult = modmult(bc(n-d, k), innersum);
    //    assert(innermult >= 0);
      //  printf("debug_k_innermult: %ld\n", innermult);
        result = (result + innermult) % P;
    }
  //  assert(result >= 0);
  //  printf("solve2(%ld, %ld)=%ld\n", index1, index2, result);
    return result;
}

long solve2(int index1, int index2) {
  //  printf("solve2 for %ld %ld\n", index1, index2);
    if (r[index1] < r[index2]) {
        if (dists[index1][index2] + r[index1] <= r[index2]) {
          //  printf("index2 covers index1\n");
            return solve1(index2);
        }
    } else {
        if (dists[index1][index2] + r[index2] <= r[index1]) {
         //   printf("index1 covers index2\n");
            return solve1(index1);
        }
    }
    if (dists[index1][index2] > r[index1] + r[index2]) {
       // printf("ISOLATED\n");
        return (solve1(index1) + solve1(index2)) % P;
    }
    //printf("test");
    if (r[index1] < r[index2]) {
      return (solve1(index2) + solve1_ecluding(index1, index2)) % P;   
    } else {
      return (solve1(index1) + solve1_ecluding(index2, index1)) % P;
    }
}

int other(int index1, int index2) {
    if (index1 != 0 && index2 != 0) {
        return 0;
    } else if (index1 != 1 && index2 != 1) {
        return 1;
    }
    return 2;
}

long solve1_excluding2(int index1, int index2, int index3) {
    long a = 0;
    long b = 0;
    long c = 0;
    long d = 0;
    for (int i=0; i<n; i++) {
        if (x[index1][i] == x[index2][i]) {
            if (x[index1][i] == x[index3][i]) {
                a ++;
            } else {
                b ++;
            }
        } else if (x[index1][i] == x[index3][i]) {
            c ++;
        } else {
            d ++;
        }
    }
    long result = 0;
  //  printf("debug: %ld %ld %ld\n", r1, r2, d);
    long jamin= max((long)0, max(r[index2], r[index3]) + a + 1 - n);
    for(long ja=jamin; ja<=min(r[index1], a); ja++) {
        long innersum = 0;
        long r1_ja = r[index1] - ja;
        long jbmin = max((long) 0, r[index2] - ja -c -d + 1);
        for (long jb=jbmin; jb<=min(r1_ja, b); jb++) {
            long r1_ja_jb = r1_ja - jb;
            long jcmin = max((long) 0, r[index3] - ja - (b - jb) - d + 1);
            for (long jc=jcmin; jc<=min(r1_ja_jb, c); jc++) {
                long b1 = -r1_ja_jb + jc + d;
                long b2 = r[index2] - ja - jb - c + jc + 1;
                long b3 = r[index3] - ja - b + jb -jc + 1;
                long jd_min = max( max((long) 0, b1), max(b2, b3));
                for (long jd=jd_min; jd<=d; jd++) {
                    long innermult = modmult(bc(b, jb), bc(c, jc), bc(d, jd));
                    innersum = (innersum + innermult) % P;
                }
            }
        }
        if (innersum > 0) {
            long resultmult = modmult(bc(a, ja), innersum);
            result = (result + resultmult) % P;
        }
    }
  //  printf("solve3()=%ld\n", result);
    return result;
}

long solve_hard(int index1, int index2, int index3) {

    return (solve1_excluding2(index1, index2, index3) + solve2(index2, index3)) % P;
}

// index1 and index2 are far apart
long solve3_separated(int index1, int index2, int index3) {
 // printf("solve3_separated\n");
  if (dists[index1][index3] > r[index1] + r[index3]) {
    return (solve1(index1) + solve2(index2, index3)) % P;
  }
  if (dists[index2][index3] > r[index2] + r[index3]) {
    return (solve1(index2) + solve2(index1, index3)) % P;
  }
 // printf("imroved case!\n");
  return (((solve1(index3) + solve1_ecluding(index1, index3)) % P )+ solve1_ecluding(index2, index3)) % P;
}

long solve3() {
    for (int index1=0; index1<2; index1++) {
        for (int index2=index1+1; index2 < 3; index2 ++) {
            long rmin = min(r[index1], r[index2]);
            long rmax = max(r[index1], r[index2]);
            if (dists[index1][index2] + rmin <= rmax) {
        //        printf("index1 and index2 are covering\n");
                if (r[index1] < r[index2]) {
                    return solve2(index2, other(index1, index2));
                } else {
                    return solve2(index1, other(index1, index2));
                }
            }
        }
    }
    if (dists[0][1] > r[0] + r[1]) { // 0 is isolated
    //    printf("0 is isolated\n");
      return solve3_separated(0, 1, 2);
     //   return (solve1(0) + solve2(1, 2)) % P;
    }
    if (dists[0][2] > r[0] + r[2]) { // 1 is isolated
      return solve3_separated(0, 2, 1);
      //  return (solve1(1) + solve2(0, 2)) % P;
    }
    if (dists[1][2] > r[1] + r[2]) { // 2 is isolated
      return solve3_separated(1, 2, 0);
    //    return (solve1(2) + solve2(0, 1)) % P;
    }
    //printf("hard\n");
   // return solve_hard(1, 0, 2);
    if (r[0] <= r[1]) {
      if (r[0] <= r[2]) {
        return solve_hard(0, 1, 2);
      } else {
        return solve_hard(2, 1, 0);
      }
    } else {
      if (r[1] < r[2]) {
        return solve_hard(1, 0, 2);
      } else {
        return solve_hard(2, 0, 1);
      }
    }
}

void prepopulate() {
    BC[0][0] = 1;
 //   printf("%ld %ld = %ld\n", 0, 0, BC[0][0]);
    for (long i=1; i <= n; i++) {
        BC[i][0] = 1;
   //     printf("%ld %ld = %ld\n", i, 0, BC[i][0]);
        for (long j=1; j<=i; j++) {
            BC[i][j] = (BC[i - 1][j - 1] + BC[i - 1][j]) % P;
      //      printf("%ld %ld = %ld\n", i, j, BC[i][j]);
        }
    //    printf("%ld %ld = %ld\n", i, 0, BC[i][0]);
    }
}

int main() {
//  setbuf(stdout, NULL);
  read();
  prepopulate();
  printf("%ld\n", solve3());
  return 0;
}