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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

#define REP(a, n) for (int a = 0; a < (n); ++a)
#define FOR(a, b, c) for (int a = (b); a <= (c); ++a)
#define FORD(a, b, c) for (int a = (b); a >= (c); --a)

#define INF 1000000000

typedef long long LL;

using namespace std;

//////////////////////

#define DEBUG(x) 

#define MOD (INF+7)

int noverk[10001][10001];
int novermrk[10001][10001];
int N;

inline int dla1(int R) {
    DEBUG(fprintf(stderr, "dla1 (promien %d) -> %d\n", R, novermrk[N][R]);)
    return novermrk[N][R];
}

int dla2(char *k1, int R1, char *k2, int R2) {
    int zgo = 0;
    REP(a, N)
        if (k1[a] == k2[a])
            ++zgo;
    int roz = N - zgo;
    LL res = 0;
    FOR(j1, max(0, roz - R2), min(R1, roz)) {
        int z1 = roz - j1;
        int top_j0 = min(zgo, min(R1 - j1, R2 - z1));
        DEBUG(fprintf(stderr, "top: %d*%d\n", noverk[roz][j1], novermrk[zgo][top_j0]);)
        res = (res + noverk[roz][j1] * (LL) novermrk[zgo][top_j0]) % MOD;
    }
    DEBUG(fprintf(stderr, "dla2 (zg = %d, prom = %d / %d) -> %lld\n", zgo, R1, R2, res);)
    return res;
}

char str[3][11000];
int R[3];

int ile[2][2];

LL dla3() {
    REP(b, N)
        ++ile[str[1][b] != str[0][b]][str[2][b] != str[0][b]];
    LL res = 0;
    FOR(j01, max(0, ile[0][1] - R[2]), min(ile[0][1], min(R[0], R[1]))) {
        int z01 = ile[0][1] - j01;
        FOR(j10, max(0, ile[1][0] - (R[1] - j01)), min(ile[1][0], min(R[0] - j01, R[2] - z01))) {
            int z10 = ile[1][0] - j10;
            LL xx = noverk[ile[0][1]][j01] * (LL)noverk[ile[1][0]][j10] % MOD;
            FOR(j11, max(0, max(ile[1][1] - (R[1] - j01 - z10), ile[1][1] - (R[2] - z01 - j10))), min(ile[1][1], R[0] - j01 - j10)) {
                int z11 = ile[1][1] - j11;
                int top_j00 = min(ile[0][0], min(R[0] - j01 - j10 - j11, min(R[1] - j01 - z10 - z11, R[2] - z01 - j10 - z11)));
                DEBUG(fprintf(stderr, "top (01=%d/%d, 10=%d/%d, 11=%d/%d, rem=%d/%d): %d*%d*%d*%d\n", j01, ile[0][1], j10, ile[1][0], j11, ile[1][1], top_j00, ile[0][0], 
                    noverk[ile[0][1]][j01], noverk[ile[1][0]][j10], noverk[ile[1][1]][j11], novermrk[ile[0][0]][top_j00]);)
                res += xx * (LL)noverk[ile[1][1]][j11] % MOD * novermrk[ile[0][0]][top_j00] % MOD;
            }
        }
    }
    DEBUG(fprintf(stderr, "dla3 -> %lld\n", res);)
    return res;
}

int main() {
    scanf("%d", &N);
    REP(a, 3)
        scanf("%d%s", &R[a], str[a]);
    noverk[0][0] = novermrk[0][0] = 1;
    FOR(n, 1, N)
        FOR(k, 0, N) {
            noverk[n][k] = ((k ? noverk[n - 1][k - 1] : 0) + noverk[n - 1][k]) % MOD;
            novermrk[n][k] = ((k ? novermrk[n][k - 1] : 0) + noverk[n][k]) % MOD;
        }
    LL res = 3LL * MOD;
    REP(a, 3) {
        res += dla1(R[a]);
        REP(b, a)
            res -= dla2(str[a], R[a], str[b], R[b]);
    }
    res += dla3();
    printf("%lld\n", res % MOD);
}