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
#include<bits/stdc++.h>
using namespace std;
using lld = long long;

const int MAXN = 1e4+1;
const lld mod = 1e9+7;
lld bin[MAXN+5][MAXN+5];

lld f(lld a, lld b){
	return (bin[a+1][b+1]-bin[a+1][b]+mod) % mod;
}

lld field1(int r, string& s){
	return bin[s.length()+1][r+1];
}

lld field2(int r1, string& s1, int r2, string& s2){
	lld res = 0;
	int a=0,b=0;
	for(int i=0;i<s1.length();i++)
		(s1[i] != s2[i] ? a : b)++;

	for(int p=0;p<=a;p++){
		int M = min(b, min(r1-p, r2-a+p));
		if(M >= 0)
			res = (res + (f(a,p) * bin[b+1][M+1]) % mod) % mod;
	}

	return res;
}

lld field3(int r1, string& s1, int r2, string& s2, int r3, string& s3){
	int x,y,z,t;
	x = y = z = t = 0;
	lld res = 0;

	for(int i=0;i<s1.length();i++){
		string help="";
		help += s1[i];
		help += s2[i];
		help += s3[i];
		if(help == "000" || help == "111") x++;
		if(help == "001" || help == "110") y++;
		if(help == "010" || help == "101") z++;
		if(help == "011" || help == "100") t++;
	}

	for(int b=0;b<=y;b++){
		lld m1 = f(y,b);
		for(int c=0;c<=z;c++){
			lld m2 = (m1*f(z,c)) % mod;
			for(int d=0;d<=t;d++){
				lld m3 = (m2*f(t,d)) % mod;
				int M = x;
				M = min(M, r1-y+b-z+c-d);
				M = min(M, r2-y+b-c-t+d);
				M = min(M, r3-b-z+c-t+d);
				if(M >= 0)
					res += (m3 * bin[x+1][M+1]) % mod;
			}
		}
	}

	return res;
}

void solve2(int r1, string& s1, int r2, string& s2){
	cout << (field1(r1,s1) + field1(r2,s2) + mod-field2(r1,s1, r2,s2)) % mod << "\n";
}

void solve3(int r1, string& s1, int r2, string& s2, int r3, string& s3){
	lld res = 0;
	res += field1(r1,s1);
	res += field1(r2,s2);
	res += field1(r3,s3);
	res += mod-field2(r1,s1, r2,s2);
	res += mod-field2(r2,s2, r3,s3);
	res += mod-field2(r3,s3, r1,s1);
	res += field3(r1,s1, r2,s2, r3,s3);

	cout << res%mod << "\n";
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	bin[1][1] = 1;
	for(int i=2;i<=MAXN;i++)
		for(int j=1;j<=i;j++)
			bin[i][j] = (bin[i-1][j-1] + bin[i-1][j]) % mod;

	for(int i=1;i<=MAXN;i++)
		for(int j=1;j<=i;j++)
			bin[i][j] = (bin[i][j] + bin[i][j-1]) % mod;

	int r1,r2,r3;
	string s1,s2,s3;
	cin >> r1 >> s1 >> r2 >> s2 >> r3 >> s3;

	if(r1 == r2 && s1 == s2)
		solve2(r1,s1, r3,s3);
	else if(r1 == r3 && s1 == s3)
		solve2(r1,s1, r2,s2);
	else if(r2 == r3 && s2 == s3)
		solve2(r1,s1, r3,s3);
	else
		solve3(r1,s1, r2,s2, r3,s3);

	return 0;
}