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
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>

const int MODULO{1'000'000'000 + 7};

struct Data {
  unsigned r{0};
  std::string s;
  std::vector<unsigned> v;

  bool operator<(const Data &other) const {
    return std::tie(r, s) < std::tie(other.r, other.s);
  }
};

bool Compare(char c, unsigned slen, const Data &d, unsigned &prev_diff,
             unsigned &all_smaller) {
  if (prev_diff > d.r) {
    all_smaller++;
    return false;
  }

  const auto length = d.s.length() - slen;
  auto next_diff = 0u;

  if (length > 0) {
    next_diff = d.v[length - 1];
  }

  // DEBUG
  //  std::cerr << a << " " << d.s << " r " << d.r << " p " << prev_diff << " l
  //  "
  //            << length << " n " << next_diff << std::endl;

  if (c != d.s[slen - 1]) {
    prev_diff++;
  }

  if (slen != 1 && c == '0') {
    return false;
  }

  if (prev_diff + next_diff > d.r) {
    return false;
  }

  return true;
}

struct Elem {
  std::array<unsigned, 3> diffs = {0, 0, 0};
  unsigned len{0};
  char c{0};


};

void Process(size_t n, const std::set<Data> &spheres) {
  std::queue<Elem> q;
  int count = 0;

  q.push({{0, 0, 0}, 1, '0'});
  q.push({{0, 0, 0}, 1, '1'});

  while (!q.empty()) {
    auto e = q.front();
    q.pop();

    // DEBUG
    //      std::cerr << s1 << std::endl;

    //
    unsigned all_smaller = 0;
    size_t index = 0;
    bool found = false;

    for (const auto &i : spheres) {
      if (Compare(e.c, e.len, i, e.diffs[index], all_smaller)) {
        found = true;
      }
      index++;
    }

    if (found) {
      // DEBUG
      //        std::cerr << "found: " << e.s << std::endl;

      count = (count + 1) % MODULO;
    }

    if (e.len < n && all_smaller != spheres.size()) {
      q.push({e.diffs, e.len + 1, '0'});
      q.push({e.diffs, e.len + 1, '1'});
    }
  }

  std::cout << count << std::endl;
}

int main() {
  size_t n = 0;
  std::cin >> n;

  std::set<Data> spheres;

  for (int i = 0; i < 3; ++i) {
    Data data;
    std::cin >> data.r;
    std::cin >> data.s;

    data.v.reserve(100000);

    //
    unsigned counter = 0;

    std::string copy = data.s;
    std::reverse(copy.begin(), copy.end());
    for (const auto &c : copy) {
      if (c == '1') {
        counter++;
      }
      data.v.push_back(counter);
    }

    // DEBUG
    //    for (const auto &i : data.v) {
    //      std::cerr << i << " ";
    //    }
    //    std::cerr << std::endl;
    // END DEBUG

    spheres.insert(std::move(data));
  }

  Process(n, spheres);
  return 0;
}