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

using namespace std;

const int mod = 1e9 + 7;
const int MAXN = 1e6;
typedef long long ll;
unordered_set <bitset<MAXN>> used;

void gen(bitset<MAXN> a, int n, int r, ll &res, int i, int changed)
{
	if(changed == r) return;
	if(i == n) return;
	gen(a, n, r, res, i+1, changed);
	a.flip(i);
	if(used.find(a) == used.end())
	{
		used.insert(a);
		res = (res+1)%mod;
	}
	gen(a, n, r, res, i+1, changed+1);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	
	//set<bitset<MAXN>> used;

	
	ll res = 0;
	bitset<MAXN> back1;
	bitset<MAXN> back2;
	int rB1;
	int rB2;
	ll resB1;
	ll resB2;
	
	for(int t=0; t<3; ++t)
	{
		int r;
		cin >> r;
		
		bitset<MAXN> a;

		for(int i=0; i<n; ++i)
		{
			char tmp; 
			cin >> tmp;
			if(tmp&1) a.flip(i);

		}
		if(t == 0)
		{
			rB1 = r;
			back1 = a;
		}
		if(t == 1)
		{
			rB2 = r;
			back2 = a;
		}
		if(t == 1 && r == rB1 && back1 == a)
		{
			res = (res + resB1)%mod;
			continue;
		}
		if(t == 2)
		{
			if(r == rB1 && back1 == a)
			{
				res = (res + resB1)%mod;
				continue;
			}
			else if(r == rB2 && back2 == a)
			{
				res = (res + resB2)%mod;
				continue;
			}
		}
		ll cr = 0;
		bitset<MAXN> b;
		if(used.find(a) == used.end()) used.insert(a), ++cr;
		
		gen(a, n, r, cr, 0, 0);
		
		if(t == 1)
			resB1 = cr;
		if(t == 2)
			resB2 = cr;
			
		res = (res + cr)%mod;
	}
	
	cout << res << '\n';
	
	return 0;
}
/*
3
1 000
1 100
0 111
5
2 10110
0 11010
1 00000
*/