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 #include 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()); }