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

typedef long long int lli;

const int MAXN = 10005;
const lli MOD = 1000000007;

lli r[3];
char in[MAXN];
lli a[4];

lli npk_tab[MAXN][MAXN];
lli pref[MAXN];

lli mod(lli x) {
	if (x >= 0)
		return x%MOD;
	else
		return (x%MOD)+MOD;
}

lli pot(lli x, lli n) {
	if (n == 0)
		return 1;
	if (n%2 == 0)
		return pot((x*x)%MOD, n/2);
	else
		return (x*pot(x, n-1))%MOD;
}

lli sum(lli low, lli up) {
	if (low <= 0)
		return pref[up];
	return mod(pref[up]-pref[low-1]);
}

lli npk(lli n, lli k) {
// 	printf("npk %lld %lld\n", n, k);
	if (k<0 || k > n)
		return 0;
// 	printf(" -> %lld\n", npk_tab[n][k]);
	return npk_tab[n][k];
}

void fill_npk(int n) {
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=i; j++) {
			if (j == 0 || j == i)
				npk_tab[i][j] = 1;
			else
				npk_tab[i][j] = (npk_tab[i-1][j-1]+npk_tab[i-1][j])%MOD;
		}
	}
}

int n;
vector<int> k[3];

void solve_small() {
	for (int i=0; i<n; i++) {
		int id = 2*k[1][i]+k[2][i];
		a[id]++;
	}
	
	fill_npk(max(a[0], max(a[1], max(a[2], a[3])))+1);
	
	pref[0] = 1;
	for (int i=1; i<=a[3]; i++) {
		pref[i] = (pref[i-1]+npk(a[3], i))%MOD;
	}
	
	lli res = 0;
	
	for (lli b0=0; b0<=a[0]; b0++) {
		for (lli b1=0; b1<=a[1]; b1++) {
			for (lli b2=0; b2<=a[2]; b2++) {
// 				printf("%lld %lld %lld\n", b0, b1, b2);
				lli c1 = r[0]+1-b0-b1-b2;
				lli c2 = b0+b1+a[2]-b2+a[3]-r[1]-1;
				lli c3 = b0+a[1]-b1+b2+a[3]-r[2]-1;
				
// 				printf("> %lld %lld %lld\n", c1, c2, c3);
				
				lli low = c1;
				lli up = min(c2, min(c3, a[3]));
				
				if (up < low)
					continue;
				
// 				printf(" %lld %lld\n", low, up);
				
				lli tmp = (npk(a[0], b0)*npk(a[1], b1))%MOD;
				tmp = (tmp*npk(a[2], b2))%MOD;
				tmp = (tmp*sum(low, up))%MOD;
// 				printf("  %lld\n", tmp);
				res = mod(res + tmp);
			}
		}
	}
	
	printf("%lld", mod(pot(2, n)-res));
}

int main() {
	scanf("%d", &n);
	
	for (int i=0; i<3; i++) {
		scanf("%lld%s", &r[i], in);
		for (int j=0; j<n; j++) {
			if (in[j] == '0')
				k[i].push_back(0);
			else
				k[i].push_back(1);
		}
	}
	
	for (int i=0; i<n; i++) {
		k[1][i] ^= k[0][i];
		k[2][i] ^= k[0][i];
		k[0][i] = 0;
	}
	
	solve_small();
	return 0;
}