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 | #include <algorithm>
#include <cstdio>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)
typedef long long LL;
const int mod = 1000000007;
int n;
int r[3];
char s[3][10001];
int same;
int diff[3];
LL fac[10001];
LL rfac[10001];
LL EXTEUC(LL a, LL b, LL& x, LL& y) {
x = 1;
y = 0;
LL x1 = 0, y1 = 1;
while (b != 0) {
LL t = b;
LL q = a / b;
b = a % b;
a = t;
t = x1;
x1 = x - q * x1;
x = t;
t = y1;
y1 = y - q * y1;
y = t;
}
return a;
}
inline LL MODL(LL a, LL b) {
return a >= 0 ? a % b : b + ((a + 1) % b) - 1;
}
LL REVM(LL a, LL m) {
LL x, y;
EXTEUC(m, a, x, y);
return MODL(y, m);
}
LL binom(LL n, LL k) {
return fac[n] * rfac[k] % mod * rfac[n - k] % mod;
}
LL sumBinom(LL n, LL k) {
int res = 0;
REP(i,k+1) res = (res + binom(n, i)) % mod;
return res;
}
int vol(int a) {
return sumBinom(n, r[a]);
}
int inter2(int a, int b) {
int same2 = 0;
int diff2 = 0;
REP(i,n)
if (s[a][i] == s[b][i]) ++same2;
else ++diff2;
int res = 0;
int dmi = diff2 - r[a], dma = r[b] + 1;
FOR(d0,dmi,dma) {
LL f = binom(diff2, d0);
int r0 = r[a] - diff2 + d0, r1 = r[b] - d0;
int sma = min(min(r0, r1), same2);
res = (res + (f * sumBinom(same2, sma) % mod)) % mod;
}
return res;
}
int inter3() {
int res = 0;
int d0mi = diff[0] - r[0], d0ma = min(r[1], r[2]) + 1;
FOR(d0,d0mi,d0ma) {
LL f0 = binom(diff[0], d0);
int r0 = r[0] - diff[0] + d0, r1 = r[1] - d0, r2 = r[2] - d0;
int d1mi = diff[1] - r1, d1ma = min(r0, r2) + 1;
FOR(d1,d1mi,d1ma) {
LL f1 = (f0 * binom(diff[1], d1)) % mod;
int rr0 = r0 - d1, rr1 = r1 - diff[1] + d1, rr2 = r2 - d1;
int d2mi = diff[2] - rr2, d2ma = min(rr0, rr1) + 1;
FOR(d2,d2mi,d2ma) {
LL f2 = (f1 * binom(diff[2], d2)) % mod;
int rrr0 = rr0 - d2, rrr1 = rr1 - d2, rrr2 = rr2 - diff[2] + d2;
int sma = min(min(min(rrr0, rrr1), rrr2), same);
res = (res + (f2 * sumBinom(same, sma) % mod)) % mod;
}
}
}
return res;
}
int main() {
INT(n1);
n = n1;
fac[0] = 1;
FOR(i,1,n+1) fac[i] = fac[i - 1] * i % mod;
REP(i,n+1) rfac[i] = REVM(fac[i], mod);
REP(k,3) scanf("%d%s", &r[k], &s[k]);
REP(i,n)
if (s[0][i] == s[1][i] && s[1][i] == s[2][i]) ++same;
else REP(k,3) if (s[(k + 1) % 3][i] == s[(k + 2) % 3][i]) ++diff[k];
printf("%d\n", vol(0) + vol(1) + vol(2) - inter2(0, 1) - inter2(0, 2) - inter2(1, 2) + inter3());
}
|