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
184
185
186
187
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <iostream>
#include <queue>

#define MOD 1000000007LL

typedef unsigned long long num;

using namespace std;

char *hyper_cube;

struct Sphere {
  string start;
  int r;
};


int64_t fastPow(int64_t a, int64_t exp, int64_t mod)                               
{                                                                                  
    int64_t res = 1;                                                               
    while (exp)                                                                    
    {                                                                              
        if (exp % 2 == 1)                                                          
        {                                                                          
            res *= a;                                                              
            res %= mod;                                                            
        }                                                                          

        a *= a;                                                                    
        a %= mod;                                                                  
        exp >>= 1;                                                                 
    }                                                                              
    return res;                                                                    
}                                                                                  

// This inverse works only for primes p, it uses Fermat's little theorem                                                                                   
int64_t inverse(int64_t a, int64_t p)                                              
{                                                                                                                                             
    return fastPow(a, p - 2, p);                                                   
}                                                                                  

int64_t bc(int64_t n, int64_t k, int64_t p=MOD)                                  
{                                                                                  
    std::vector<int64_t> fact(n + 1);                                              
    fact[0] = 1;                                                                   
    for (auto i = 1; i <= n; ++i)                                                  
        fact[i] = (fact[i - 1] * i) % p;                                           

    return ((((fact[n] * inverse(fact[k], p)) % p) * inverse(fact[n - k], p)) % p);
}

void mark_range(int position, int r, int &n, int &index) {
  if (r < 0) {
    return;
  }

  hyper_cube[position] = index;

  for (int i = 0; i < n; i++) {
    mark_range(position ^ (1 << i), r - 1, n, index);
  }
}

int brute_force(vector<Sphere> &spheres, int &n) {
  int result = 0;

  hyper_cube = new char[1<<n];

  for (int i=0; i<1<<n; i++){
    hyper_cube[i] = 0;
  }

  for (int i = 1; i <= spheres.size(); i++) {
    mark_range(stoi(spheres[i - 1].start, 0, 2), spheres[i - 1].r, n, i);
  }

  for (int i = 0; i < 1<<n; i++) {
    if (hyper_cube[i]) {
      result++;
    }
  }

  return result;
}

unsigned long long brute_force2(vector<Sphere> &spheres, unsigned long long &n) {
  unsigned long long result = 0;
  vector<unsigned long long> spheres_int_starts(spheres.size());

  for(int i=0; i<spheres.size(); i++) {
    spheres_int_starts[i] = stoi(spheres[i].start, 0, 2);
  }

  for (unsigned long long i=0; i<1LL<<n; i++) {
    for (int j=0; j<spheres.size(); j++) {
      // printf("%u %u %lld %d %d\n", i, spheres_int_starts[j], (i^spheres_int_starts[j])&((1LL<<(n))-1), __builtin_popcountll((i^spheres_int_starts[j])&((1<<(n))-1)), spheres[j].r);
      if (__builtin_popcountll((i^spheres_int_starts[j])&((1LL<<(n))-1)) <= spheres[j].r) {
        result++;
        result %= 1000000007LL;
        break;
      }
    }
  }

  return result;
}

int get_common_bits(Sphere &A, Sphere &B) {
  int result = 0;

  for(int i=0; i<A.start.length(); i++) {
    if (A.start[i] == B.start[i]) {
      result++;
    }
  }

  return result;
}

unsigned long long solve_for_2(vector<Sphere> &spheres, unsigned long long &n) {
  unsigned long long result = 0;

  for (int i=0; i<spheres.size(); i++) {
    for (int j=0; j<=spheres[i].r; j++) {
      result += bc(n, j);
      result %= MOD;

      // printf("%d %d %ld\n", n, j, bc(n, j));
    }
  }

  int common_amount = get_common_bits(spheres[0], spheres[1]);

  for (int i=0; i<=common_amount; i++) {
    unsigned long long common_bc = bc(common_amount, i);
    for (int j=0; j<=n-common_amount; j++) {
      // printf("%d %d %d %d\n", i + j, spheres[0].r, n-(i+j), spheres[1].r);
      if (i + j <= spheres[0].r && n-(i+j) <= spheres[1].r) {
        result -= common_bc*bc(n-common_amount, j);
        result = (result%MOD+MOD)%MOD;
      }
    }
  }

  return result % MOD;
}

int main() {
  unsigned long long n;
  vector<Sphere> spheres(3);

  scanf("%lld", &n);

  for (int i=0; i<3; i++) {
    cin >> spheres[i].r >> spheres[i].start;
  }

  if (spheres.size() == 3 && spheres[0].start == spheres[1].start) {
    if (spheres[0].r > spheres[1].r) {
      spheres.erase(spheres.begin() + 1);
    } else {
      spheres.erase(spheres.begin());
    }
  }

  if (spheres.size() == 3 && spheres[0].start == spheres[2].start) {
    if (spheres[0].r > spheres[2].r) {
      spheres.erase(spheres.begin() + 2);
    } else {
      spheres.erase(spheres.begin());
    }
  }

  if (spheres.size() == 3 && spheres[1].start == spheres[2].start) {
    if (spheres[1].r > spheres[2].r) {
      spheres.erase(spheres.begin() + 2);
    } else {
      spheres.erase(spheres.begin() + 1);
    }
  }

  printf("%lld\n", brute_force2(spheres, n));
}