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
#include "bits/stdc++.h"

using namespace std;

const int MOD = 1'000'000'007;

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  vector <int> r(3);
  vector <string> s(3);
  for (int i=0; i<3; i++) cin >> r[i] >> s[i];
  vector <vector <int>> binom(n+1, vector<int>(n+1));
  for (int i=0; i<=n; i++) {
    binom[i][0] = 1;
    for (int j=1; j<=i; j++) binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % MOD;
  }
  auto volume = [&](int b1) {
    int ret = 0;
    for (int i=0; i<=r[b1]; i++) ret = (ret + binom[n][i])%MOD;
    // cerr << "V1 = " << ret << "\n";
    return ret;
  };
  auto volume2 = [&](int b1, int b2) {
    int ret = 0, common = 0;
    for (int i=0; i<n; i++) if (s[b1][i] == s[b2][i]) common++;
    for (int i=0; i<=common; i++) {
      for (int j=0; j<=n-common; j++) {
        if (i+j <= r[b1] and i-j+n-common <= r[b2]) {
          ret = (ret + 1LL * binom[common][i] * binom[n-common][j] % MOD) % MOD;
        }
      }
    }
    // cerr << "V2 = " << ret << "\n";
    return ret;
  };
  auto volume3 = [&](int b1, int b2, int b3) {
    int common2 = 0, differ2 = 0;
    for (int i=0; i<n; i++) {
      if (s[b1][i] == s[b2][i] and s[b1][i] == s[b3][i]) common2++;
      if (s[b1][i] != s[b2][i] and s[b1][i] != s[b3][i]) differ2++;
    }
    int sum = common2 + differ2;
    vector <vector<int> > calc(sum+1, vector<int>(sum+1));
    for (int i=0; i<=common2; i++) {
      for (int j=0; j<=differ2; j++) {
        int& where = calc[i+j][i-j+differ2];
        where = (where + 1LL * binom[common2][i] * binom[differ2][j] % MOD) % MOD;
      }
    }
    for (int i=0; i<=sum; i++) {
      for (int j=0; j<sum; j++) calc[i][j+1] = (calc[i][j+1] + calc[i][j]) % MOD;
    }
    for (int i=0; i<sum; i++) {
      for (int j=0; j<=sum; j++) calc[i+1][j] = (calc[i+1][j] + calc[i][j]) % MOD;
    }

    int common12 = 0, common13 = 0;
    for (int i=0; i<n; i++) {
      if (s[b1][i] == s[b2][i] and s[b1][i] != s[b3][i]) common12++;
      if (s[b1][i] == s[b3][i] and s[b1][i] != s[b2][i]) common13++;
    }

    int ret = 0;
    for (int i=0; i<=common12; i++) {
      for (int j=0; j<=common13; j++) {
        int same = r[b1] - i - j;
        int rest = min(r[b2] - i + j - common13, r[b3] - j + i - common12);
        if (min(same, rest) >= 0) {
          ret = (ret + (1LL * binom[common12][i] * binom[common13][j] % MOD
              * calc[min(sum, same)][min(sum, rest)] % MOD)) % MOD;
        }
      }
    }
    // cerr << "V3 = " << ret << "\n";
    return ret;
  };
  cout << ((0LL + volume(0) + volume(1) + volume(2)
    - volume2(0, 1) - volume2(1, 2) - volume2(2, 0)
    + volume3(0, 1, 2)) % MOD + MOD) % MOD << "\n";
}