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
128
129
130
131
132
133
134
135
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; 

#define MOD 1000000007
int n;
int r1,r2,r3;

// Extended Euclidean algorithm
int xGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (long long)(a / b) * y1;
    return gcd;
}

// factorial of n modulo MOD
int modfact(int n) {
    int result = 1;
    while (n > 1) {
        result = (long long)result * n % MOD;
        n -= 1;
    }
    return result;
}

// multiply a and b modulo MOD
int modmult(int a, int b) { return (long long)a * b % MOD; }

// inverse of a modulo MOD
int inverse(int a) {
    int x, y;
    xGCD(a, MOD, x, y);
    return x;
}

// binomial coefficient nCk modulo MOD
int bc(int n, int k)
{
    return modmult(modmult(modfact(n), inverse(modfact(k))), inverse(modfact(n - k))) + MOD;
}

int size(int r) {
	int result = 0;
	for (int i=0;i<=r;i++) {
		result = (result + bc(n, i)) % MOD;
	}
	return result;
}

int count1(char *s) {
	int r = 0;
	for(int i=0;i<n;i++) {
		if(s[i] == '1') r++;
	}
	return r;
}

int diff(char *s1, char*s2) {
	int r = 0;
	for(int i=0;i<n;i++) {
		if(s1[i] != s2[i]) r++;
	}
	return r;
}

int intersect2(int r1, char* s1, int r2, char* s2) {
	
	int dif = diff(s1,s2);
	// wspolny srodek
	if (dif == 0) {
		if( r1 < r2) return size(r1);
		else return size(r2);
	}
	// rozdzielne
	if (dif > r1 + r2) return 0;

	// pierwsza zawiera druga
	if (r1 >= dif + r2) return size(r2);
	
	// druga zawiera pierwszą
	if (r2 >= dif + r1) return size(r1);
	
	// przecinają sie
	int result = 0;
	for(int i=dif - r2; i<=r1; i++) {
		result = (result + bc(dif, i)) % MOD;
	} 
	
	return result;
}

int main() {	
	scanf("%d", &n);
	char* s1 = new char[n]();
	char* s2 = new char[n]();
	char* s3 = new char[n]();
	
	scanf("%d %s", &r1, s1);
	scanf("%d %s", &r2, s2);
	scanf("%d %s", &r3, s3);
	
	// identyczne 3
	if (r1 == r2 && r2 == r3 && strcmp(s1,s2) == 0 && strcmp(s2,s3) == 0) {
		printf("%d\n", size(r1));
		return 0;
	}

	if (r1 == r2 && strcmp(s1,s2) == 0) { 	// pierwsza i druga identyczne
		printf("%d\n", (size(r1) + size(r3) - intersect2(r1,s1,r3,s3)) % MOD); // nie biore drugiej
	} else if (r1 == r2 && strcmp(s1,s3) == 0) { // pierwsza i trzecia identyczne
		printf("%d\n", (size(r1) + size(r2) - intersect2(r1,s1,r2,s2)) % MOD); // nie biore trzeciej
	} else if (r2 == r3 && strcmp(s2,s3) == 0) { // druga i trzecia identyczne
		printf("%d\n", (size(r1) + size(r2) - intersect2(r1,s1,r2,s2)) % MOD); // nie biore trzeciej
	} else {	
		// printf("%d %d %d\n", size(r1),size(r2) , size(r3));
// 		printf("%d \n", intersect2(r1,s1,r2,s2));
// 		printf("%d \n", intersect2(r1,s1,r3,s3));
// 		printf("%d \n", intersect2(r2,s2,r3,s3));
//		
		int result = (size(r1) + size(r2) + size(r3)) % MOD;
		result = (result - intersect2(r1,s1,r2,s2)) % MOD;
		result = (result - intersect2(r1,s1,r3,s3)) % MOD;
		result = (result - intersect2(r2,s2,r3,s3)) % MOD;
		
		printf("%d\n", result);
	}	
}