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
#include <cstdio>

const int max_n = 10001;
long long int p = 1000000007LL;

long long int brute_force_check(int n, unsigned long long int s1,
                                unsigned long long int s2,
                                unsigned long long int s3, int r1, int r2,
                                int r3) {
  long long int result = 0LL;

  for (unsigned long long int i = 0ULL; i < (1ULL << n); i++) {
    int d1 = n - (__builtin_popcount(i & s1) +
                  __builtin_popcount((~i) & (~s1) & ((1 << n) - 1)));
    int d2 = n - (__builtin_popcount(i & s2) +
                  __builtin_popcount((~i) & (~s2) & ((1 << n) - 1)));
    int d3 = n - (__builtin_popcount(i & s3) +
                  __builtin_popcount((~i) & (~s3) & ((1 << n) - 1)));
    if (d1 <= r1 || d2 <= r2 || d3 <= r3) {
      result++;
    }
  }

  return result;
}

int main() {
  int n, r[3];
  char s[3][max_n];

  scanf("%d", &n);

  for (int i = 0; i < 3; i++) {
    scanf("%d", &r[i]);
    scanf("%s", &s[i][0]);
  }

  unsigned long long int s_int[3];
  s_int[0] = s_int[1] = s_int[2] = 0;

  for (int i = 0; i < n; i++) {
    s_int[0] |= (((s[0][i] == '0') ? 0ULL : 1ULL) << i);
    s_int[1] |= (((s[1][i] == '0') ? 0ULL : 1ULL) << i);
    s_int[2] |= (((s[2][i] == '0') ? 0ULL : 1ULL) << i);
  }

  printf(
      "%lld\n",
      brute_force_check(n, s_int[0], s_int[1], s_int[2], r[0], r[1], r[2]) % p);

  return 0;
}