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

using namespace std;

const long long inf = 1e9+7;

int n, r[3];
bitset<10001> s[3];

long long bad()
{
    vector<vector<vector<long long> > > dp(vector<vector<vector<long long> > >(n + 1, vector<vector<long long> >(n + 1, vector<long long>(n + 1, 0)))), old;

    dp[s[0][0]][s[1][0]][s[2][0]] = dp[!s[0][0]][!s[1][0]][!s[2][0]] = 1;
    int xor1 = s[0][0] != s[1][0], xor2 = s[0][0] != s[2][0], xor3 = s[1][0] != s[2][0];

    for (int l = 1; l < n; l++)
    {
        old = dp;
        dp.assign(n + 1, vector<vector<long long> >(n + 1, vector<long long>(n + 1, 0)));

        if (s[0][l] != s[1][l])
            ++xor1;
        if (s[0][l] != s[2][l])
            ++xor2;
        if (s[1][l] != s[2][l])
            ++xor3;
        dp[0][xor1][xor2] = 1;
        dp[xor1][0][xor3] = 1;
        dp[xor2][xor3][0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                {
                    dp[i][j][k] = old[i - s[0][l]][j - s[1][l]][k - s[2][l]] + old[i - !s[0][l]][j - !s[1][l]][k - !s[2][l]];
                    if (dp[i][j][k] >= inf)
                        dp[i][j][k] -= inf;
                }
    }

    long long odp = 0;
    for (int i = r[0] + 1; i <= n; i++)
        for (int j = r[1] + 1; j <= n; j++)
            for (int k = r[2] + 1; k <= n; k++)
            {
                odp += dp[i][j][k];
                if (odp >= inf)
                    odp -= inf;
            }
    return odp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < 3; i++)
    {
        string temp;
        cin >> r[i] >> temp;
        for (int j = 0; j < n; j++)
            s[i][j] = (bool)(temp[j] - '0');
    }

    long long odp = 1;
    for (int i = 0; i < n; i++)
    {
        odp <<= 1;
        if (odp >= inf)
            odp -= inf;
    }
    
    odp -= bad();
    cout << (odp < 0 ? odp + inf : odp) << '\n';
}