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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <iostream>
#include <tuple>

int32_t mod = 1000000007;

const int MAX = 10005;

int32_t N[MAX][MAX];
int32_t SI[MAX];
int32_t SB[MAX];

void InitN(int d)
{
    for (int n=0;n<=d;++n)
        N[n][0] = N[n][n] = 1;
    for (int n=1;n<=d;++n)
        for (int k=1;k<d;++k)
            N[n][k] = (N[n-1][k] + N[n-1][k-1]) % mod;
}

inline int32_t D(int32_t r2, int32_t b, int32_t r, int32_t d)
{
    int32_t toMove = abs(r2-r);
    int32_t idle = (b-toMove)/2;
    if (toMove+2*idle != b) return 0;
    if (r2 <= r) {
        if (toMove + idle > r) return 0;
        return int64_t(N[r][toMove+idle]) * N[d-r][idle] % mod;
    } else {
        if (toMove + idle > d-r) return 0;
        return int64_t(N[r][idle]) * N[d-r][toMove+idle] % mod;
    }
}

int32_t PA(int32_t d, int32_t r) {
    int32_t sum = 0;
    for (int32_t k=0;k<=r;++k) {
        sum = (sum + N[d][k]) % mod;
    }
    return sum;
}

int32_t PAB(int32_t d, int32_t ab, int32_t ra, int32_t rb) {
    int32_t sum = 0;
    for (int32_t r2=0;r2<=rb;++r2) { // dst r
        for (int32_t b=0;b<=ra;++b) { // bits to change
            sum = (sum + D(r2, b, ab, d)) % mod;
        }
    }
    return sum;
}

int32_t PABC(int32_t ab, int32_t ac, int32_t a, int32_t abc, int32_t ra, int32_t rb, int32_t rc) {
    int32_t sum = 0;
    // std::clog << "# " << abc << " " << a << std::endl;
    // std::clog << "# " << ab << " " << ac << std::endl;
    for (int32_t j=0;j<ab+ac;++j) SB[j] = SI[j] = 0;
    for (int32_t i=ra;i>=0;--i) {
        // std::clog << "#$";
        for (int32_t j=0;j<=ab+ac;++j) {
            SI[j] = (SI[j] + D(j, ra-i, ab, ab+ac)) % mod;
            // std::clog << " " << SI[j];
        }
        // std::clog << std::endl;
        for (int32_t j=0;j<=ab+ac;++j) {
            SB[j+1] = (SB[j] + SI[j]) % mod;
        }
        for (int32_t ap=0;ap<=abc+a;++ap) {
            int32_t max_ab = std::min(rb-ap, ab+ac);
            int32_t max_ac = std::min(rc-ap, ab+ac);
            int32_t min_ab = ab+ac-max_ac;
            if (min_ab > max_ab) min_ab = max_ab+1;
            // std::clog << " :: " << i << "x" << ap << " = " << min_ab << " " << max_ab << " " << D(ap, i, abc, a+abc) << std::endl;
            // abp in min_ab..max_ab -> ap+abp <= rb & ap+acp <= rc
            sum = (sum + int64_t(D(ap, i, abc, a+abc)) * (SB[max_ab+1] - SB[min_ab]) ) % mod;
        }
    }
    return sum;
}

int32_t diff(int32_t d, const std::string &a, const std::string &b)
{
    int32_t sum = 0;
    for (int i=0;i<d;++i)
        if (a[i] != b[i])
            ++sum;
    return sum;
}

std::tuple<int32_t,int32_t,int32_t,int32_t>
    cmp(int32_t d, const std::string &a, const std::string &b, const std::string &c)
{
    int32_t aa = 0, abc = 0, ab = 0, ac = 0;
    for (int i=0;i<d;++i) {
        if (a[i] != b[i] && a[i] != c[i]) {
            ++abc;
        } else if (a[i] != b[i]) {
            ++ab;
        } else if (a[i] != c[i]) {
            ++ac;
        } else {
            ++aa;
        }
    }
    return {aa, abc, ab, ac};
}

/*
#include <bitset>
#include <string>
constexpr int DD = 5;
const int64_t MK = 1 << DD;
bool F[MK];

void BruteI()
{
    for (int64_t k1=0;k1<MK;++k1)
            F[k1] = false;
}

void BruteK(int64_t k, int64_t r)
{
    for (int64_t k1=0;k1<MK;++k1)
        if (__builtin_popcount(k1^k) <= r)
            F[k1] = true;
}
int64_t BruteC()
{
    int64_t s = 0;
    for (int64_t k1=0;k1<MK;++k1)
            s += F[k1] ? 1 : 0;
    return s;
}

int64_t testSolve(int64_t k1,int64_t k2,int64_t k3,int64_t ra,int64_t rb,int64_t rc)
{
    std::string a = std::bitset<DD>(k1).to_string();
    std::string b = std::bitset<DD>(k2).to_string();
    std::string c = std::bitset<DD>(k3).to_string();
    int64_t aa = 0, abc = 0, ab = 0, ac = 0;
    std::tie(aa, abc, ab, ac) = cmp(DD,a,b,c);

    return
        ( PA(DD, ra) + PA(DD, rb) + PA(DD, rc)
        - PAB(DD, diff(DD,a,b), ra, rb)
        - PAB(DD, diff(DD,b,c), rb, rc)
        - PAB(DD, diff(DD,a,c), ra, rc)
        + PABC(ab, ac, aa, abc, ra, rb, rc)) % mod;
}

void Test() {
    int64_t MAXX = MK*MK*MK*(DD+1)*(DD+1)*(DD+1);
    std::clog << MAXX << std::endl;
    int64_t count = 0;
    double last = -1;
    for (int64_t k1=0;k1<MK;++k1)
        for (int64_t k2=0;k2<MK;++k2)
            for (int64_t k3=0;k3<MK;++k3)
                for (int64_t r1=0;r1<=DD;++r1)
                    for (int64_t r2=0;r2<=DD;++r2)
                        for (int64_t r3=0;r3<=DD;++r3) {
                            ++count;
                            if (double(count)/MAXX - last > 1e-2)
                            {
                                last = double(count)/MAXX;
                                std::clog << int(last*100) << "%" << std::endl;
                            } 
                            BruteI();
                            BruteK(k1, r1);
                            BruteK(k2, r2);
                            BruteK(k3, r3);
                            int64_t brute = BruteC();
                            int64_t solution = testSolve(k1,k2,k3,r1,r2,r3);
                            if (brute != solution) {
                                std::cout << "FAIL " << brute << " vs " << solution << std::endl;
                                std::cout << D << std::endl;
                                std::cout << r1 << " " << std::bitset<DD>(k1) << std::endl;
                                std::cout << r2 << " " << std::bitset<DD>(k2) << std::endl;
                                std::cout << r3 << " " << std::bitset<DD>(k3) << std::endl;
                            }
                        }
}
*/
int main() {
    std::ios_base::sync_with_stdio(0);

    // InitN(DD+2);
    // Test();
    // return 0;

    int32_t d, ra,rb,rc;
    std::string a,b,c;
    std::cin >> d;
    InitN(d+2);
    std::cin >> ra >> a;
    std::cin >> rb >> b;
    std::cin >> rc >> c;

    int32_t aa = 0, abc = 0, ab = 0, ac = 0;
    std::tie(aa, abc, ab, ac) = cmp(d,a,b,c);

    // std::clog << PA(d, ra) << " + " << PA(d, rb) << " + " <<  PA(d, rc) << std::endl;
    // std::clog << " - " << PAB(d, diff(d,a,b), ra, rb) << " - " << PAB(d, diff(d,b,c), rb, rc) << " - " <<  PAB(d, diff(d,a,c), ra, rc) << std::endl;
    // std::clog << " + " << PABC(ab, ac, aa, abc, ra, rb, rc) << std::endl;

    int32_t sum = 
        ( PA(d, ra) + PA(d, rb) + PA(d, rc)
        - PAB(d, diff(d,a,b), ra, rb)
        - PAB(d, diff(d,b,c), rb, rc)
        - PAB(d, diff(d,a,c), ra, rc)
        + PABC(ab, ac, aa, abc, ra, rb, rc)) % mod;
    if (sum < 0) sum += mod;
    std::cout << sum << std::endl;
    return 0;
}