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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;

ll fme(ll a, ll b){
    ll r = 1;
    while(b) {
        if(b&1) 
            r=r*a%MOD;
        a=a*a % MOD; 
        b>>=1;
    }
    return r;
}

const int MAXN = 10019;
ll fact[MAXN];
ll invFact[MAXN];

void precalc() {
    fact[0] = invFact[0] = 1;
    for(ll i=1;i<MAXN;i++) {
        fact[i] = fact[i-1]*i%MOD;
        invFact[i] = fme(fact[i],MOD-2);
    }
}

ll nck(ll n, ll k) {
    if(k > n || k < 0)
        return 0;
    return fact[n]*invFact[k]%MOD*invFact[n-k]%MOD;
}

vector<ll> sumNckLower(int n) {
    vector<ll> res(n+1);
    res[0] = 1;
    for(int i=1;i<=n;i++) {
        res[i] = (res[i-1] + nck(n,i))%MOD;
    }
    return res;
}

ll solve2(int p, int q, const string& x, const string& y) {
    int n=0,m=0;
    for(int i=0;i<(int)x.size();i++) {
        if(x[i] == y[i])
            m++;
        else
            n++;
    }

    auto S = sumNckLower(m);
    ll res = 0;
    for(int i=0;i<=(int)n;i++) {
        int L = min(min(p-i,q-n+i),m);
        if(L < 0)
            continue;
        res = (res + nck(n,i)*S[L])%MOD;
    }
    return res;
}

ll solve3(int p, int q,int t, const string& x, const string& y, const string& z) {
    int n1=0,n2=0,n3=0,m=0;
    for(int i=0;i<(int)x.size();i++) {
        if(x[i] == y[i] && y[i] == z[i])
            m++;
        else if(x[i] == y[i])
            n1++;
        else if(x[i] == z[i])
            n2++;
        else {
            assert(y[i] == z[i]);
            n3++;
        }
    }
    auto S = sumNckLower(m);
    ll res = 0;
    for(int i=0;i<=min((q+p-n2-n3)/2,n1);i++) {
        for(int j=0;j<=min(p-i,n2);j++) {
            for(int k=n3+i+j-p;k<=(int)min(n3,q+j-i-n2);k++) {
                int L = min(min(p-i-j-n3+k,q-i-k-n2+j),min(t-j-k-n1+i,m));
                if(L < 0)
                    continue;   
                res = (res + nck(n1,i)*nck(n2,j)%MOD*nck(n3,k)%MOD*S[L])%MOD;
            }
        }
    }
    return res;
}

ll solve1(int r, int d) {
    auto res = sumNckLower(d);
    return res[min(r,d)];
}

#define st first
#define nd second

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    precalc();
    int d;
    cin >> d;
    vector<pair<int,string> > tab(3);
    for(int i=0;i<3;i++)
        cin >> tab[i].st >> tab[i].nd;
    sort(tab.begin(),tab.end());
    tab.erase(unique(tab.begin(),tab.end()),tab.end());
    if(tab.size() == 1) {
        cout<<solve1(tab[0].st,d)<<"\n";
    }
    else if(tab.size() == 2) {
        ll res = solve1(tab[0].st,d) + solve1(tab[1].st,d) - solve2(tab[0].st,tab[1].st,tab[0].nd,tab[1].nd);
        res = (res%MOD+MOD)%MOD;
        cout<<res<<"\n";
    }
    else {
        ll res = solve1(tab[0].st,d) + solve1(tab[1].st,d) + solve1(tab[2].st,d)
                - solve2(tab[0].st,tab[1].st,tab[0].nd,tab[1].nd) - solve2(tab[0].st,tab[2].st,tab[0].nd,tab[2].nd) - solve2(tab[1].st,tab[2].st,tab[1].nd,tab[2].nd)
                + solve3(tab[0].st,tab[1].st,tab[2].st,tab[0].nd,tab[1].nd,tab[2].nd);
        res = (res%MOD+MOD)%MOD;
        cout<<res<<"\n";
    }
}