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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int P = 1000000007;

int pot(long long a, int n) {
	long long w=1,p=a;
	while (n) {
		if (n%2) w=w*p%P;
		p=p*p%P;
		n/=2;
	}
	return w;
}


vector<long long> silnia,inv;
void prep(int n) {
	silnia.resize(n+1);
	inv.resize(n+1);
	silnia[0]=1;
	for (int i=1;i<=n;i++)
		silnia[i]=silnia[i-1]*i%P;
	inv[n]=pot(silnia[n],P-2);
	for (int i=n;i>0;i--)
		inv[i-1]=inv[i]*i%P;
}

long long newton(int n, int k) {
	return silnia[n]*inv[k]%P*inv[n-k]%P;
}

vector<int> D(4,0);

void prep2(string s[]) {
	for (int i=0;i<s[1].length();i++)
		if (s[1][i]==s[2][i])
			if (s[2][i]==s[3][i])	D[0]++;
			else					D[3]++;
		else
			if (s[2][i]==s[3][i])	D[1]++;
			else					D[2]++;
	//for(auto &it:D) cout << it<<" ";cout << endl;
}


long long dwie(int n, int k1, int k2, int R[]) {
	int dist = D[k1]+D[k2];
	vector<long long> rest(n-dist+1,1);
	for (int i=1;i<=n-dist;i++) rest[i]=(rest[i-1]+newton(n-dist,i))%P;
	//for (auto &it:rest)cout << it<<" ";cout << endl;
	int a=max(dist-R[k2],0), b=min(dist,R[k1]);
	//cout << a << " "<<b<<endl;
	int w=0;
	for (int i=a;i<=b;i++) {
		int c = min(min(R[k1]-i,R[k2]-(dist-i)),n-dist);
		//cout << "c="<<c <<endl;
		w=(w+newton(dist,i)*rest[c])%P;
	}
	return w;
}

long long trzy(int n, int R[]) {
	vector<long long> S0,N2,N3;
	S0.resize(D[0]+1,1);
	for (int i=1;i<=D[0];i++)
		S0[i]=(S0[i-1]+newton(D[0],i))%P;
	//for (auto &it:S0)cout << it<<" ";cout << endl;
	N2.resize(D[2]+1,1);
	for (int i=1;i<D[2];i++) N2[i]=newton(D[2],i);
	N3.resize(D[3]+1,1);
	for (int i=1;i<D[3];i++) N3[i]=newton(D[3],i);
	int w=0;
	int dist2=D[1]+D[2], dist3=D[1]+D[3];
	for (int i=0;i<=D[1];i++) {
		long long m=newton(D[1],i);
		//cout << "i="<<i<<" dist2="<<dist2<<" dist3="<<dist3<<endl;
		for (int j=0;j<=D[2];j++) {
			long long m1 = m*N2[j]%P;
			for (int k=0;k<=D[3];k++) {
				//cout << "j="<<j<<" k="<<k<<" m1="<<m1<<endl;
				if (i+j+k>R[1] || dist2-i-j+k>R[2] || dist3-i+j-k>R[3]) continue;
				long long m2 = m1*N3[k]%P;
				//cout << "m2="<<m2 << endl;
				int c = min(D[0],min(min(R[1]-i-j-k,R[2]-(dist2-i-j+k)),R[3]-(dist3-i+j-k)));
				//cout << "c="<<c<<endl;
				w=(w+m2*S0[c])%P;
			}
		}
	}
	return w;
}


int d(int a, int b) {
	return __builtin_popcount(a^b);
}



int main() {
	ios_base::sync_with_stdio(0);
	int n;
	int R[4];
	string S[4];
	cin >> n;
	prep(n);
	for (int i=1;i<=3;i++) cin >> R[i] >> S[i];
	prep2(S);
	vector<long long> S3(max(R[1],max(R[2],R[3]))+1,1);
	for (int i=1;i<S3.size();i++) S3[i]=(S3[i-1]+newton(n,i))%P;
	int ans=(S3[R[1]]+S3[R[2]]+S3[R[3]])%P;
	ans=(ans+P-(dwie(n,1,2,R)+dwie(n,1,3,R)+dwie(n,2,3,R))%P)%P;
	ans=(ans+trzy(n,R))%P;
	cout << ans <<endl;
	return 0;
}