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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<iostream>
#include<bits/stdc++.h> 
using namespace std;

#define MOD 1000000007

// A Lucas Theorem based solution to compute nCr % p 

  
// Returns nCr % p.  In this Lucas Theorem based program, 
// this function is only called for n < p and r < p. 

int difference(string a, string b){
	int R=0;
	for(int i=0; i< a.size(); i++){
		if (a[i]!=b[i]){
			R++;
		}
	}
	return R;
}


int nCrModpDP(int n, int r, int p) 
{ 
    // The array C is going to store last row of 
    // pascal triangle at the end. And last entry 
    // of last row is nCr 
    int C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; // Top row of Pascal Triangle 
  
    // One by constructs remaining rows of Pascal 
    // Triangle from top to bottom 
    for (int i = 1; i <= n; i++) 
    { 
        // Fill entries of current row using previous 
        // row values 
        for (int j = min(i, r); j > 0; j--) 
  
            // nCj = (n-1)Cj + (n-1)C(j-1); 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
}

int pow(int x, int n){
	int wy = x;
	if(n==0){
		return 1;
	}
	for(int i = 1; i<n; i++){
		x= (x*wy)%MOD;
	}
	return x;
}

int value_of_hiper(int r, int n){
	int sum = 0;
	for(int i=0; i<=r; i++){
		sum = (sum+nCrModpDP(n,i,MOD)%MOD);
	}
	return sum;
}

int intersection2( int r_1, int r_2, int R, int W){
	int sum=0;
	int r_min;
	int r_max;
	
	if(r_1>r_2){
		r_max=r_1;
		r_min =r_2;
	}else{
		r_max=r_2;
		r_min=r_1;
	}
	
	int W_count = 0;
	
	while(r_min+r_max>=R){
		int W_sum = nCrModpDP(W, W_count, MOD);
		int R_sum = 0;
		int t_r_max = r_max;
		int t_r_min = r_min;
		while(t_r_max+t_r_min>=R){
			if(t_r_min>=R){
				R_sum = (R_sum + pow(2,R))%MOD;
				break;
			}else{
				R_sum = (R_sum + nCrModpDP(R, t_r_min, MOD));
				t_r_min--;
			}
		}
		sum = (sum + (W_sum*R_sum)%MOD)%MOD;
		W_count++;
		r_max--;
		r_min--;
	}
	
	return sum;
}


int main(){
	int n;
	cin >> n;
	
	int sum;
	
	int r_a;
	int r_b;
	int r_c;
	
	string hiper_a;
	string hiper_b;
	string hiper_c;
	
	cin >> r_a >> hiper_a;
	cin >> r_b >> hiper_b;
	cin >> r_c >> hiper_c;
	
	bool same = false;
	
	int r_d;
	int r_e;
	string hiper_d;
	string hiper_e;
	
	if(r_a==r_b and hiper_a==hiper_b){
		r_d = r_a;
		hiper_d = hiper_a;
		r_e = r_c;
		hiper_e = hiper_c;
		same = true;
	}else if(r_b==r_c and hiper_b==hiper_c){
		r_d = r_b;
		hiper_d = hiper_b;
		r_e = r_a;
		hiper_e = hiper_a;
		same = true;
	}else if(r_c==r_a and hiper_c==hiper_a){
		r_d = r_c;
		hiper_d = hiper_c;
		r_e = r_b;
		hiper_e = hiper_b;
		same = true;
	}
	if(same){
		int R_DE = difference(hiper_d,hiper_e);
		int W_DE = hiper_d.size() - R_DE;
		
		sum = (sum + value_of_hiper(r_d, n))%MOD;
		sum = (sum + value_of_hiper(r_e, n))%MOD;
		sum = (sum - intersection2(r_d,r_e,R_DE,W_DE))%MOD;
	}else{
		int R_AB = difference(hiper_a,hiper_b);
		int W_AB = hiper_a.size() - R_AB;
		
		int R_BC = difference(hiper_b,hiper_c);
		int W_BC = hiper_b.size() - R_BC;
		
		int R_CA = difference(hiper_c,hiper_a);
		int W_CA = hiper_c.size() - R_CA;
		
		
		sum = (sum + value_of_hiper(r_a, n))%MOD;
		//cout << sum << endl;
		sum = (sum + value_of_hiper(r_b, n))%MOD;
		//cout << sum << endl;
		sum = (sum + value_of_hiper(r_c, n))%MOD;
		//cout << sum << endl;
		sum = (sum - intersection2(r_a,r_b,R_AB,W_AB))%MOD;
		//cout << sum << endl;
		sum = (sum - intersection2(r_b,r_c,R_BC,W_BC))%MOD;
		//cout << sum << endl;
		sum = (sum - intersection2(r_c,r_a,R_CA,W_CA))%MOD;
	}
	
	cout << sum << endl;
	
}