Руководители школ очарованы эволюционированием, произошедшим в специальном лагере. Поэтому им было интересно узнать секрет эволюционирования.
Организаторы лагеря дали руководителям Покеблок — последовательность из n ингредиентов. Каждый ингредиент имеет тип 0 или 1. Организаторы сказали руководителям, что чтобы покемон типа k (k ≥ 2) эволюционировал, необходимо сделать k разрезов Покеблока, получая меньшие блоки.
Пусть Покеблок это последовательность b0b1b2... bn - 1. Разрезы можно делать в n + 1 местах, то есть до b0, между b0 и b1, между b1 и b2, ..., между bn - 2 и bn - 1, и после bn - 1.
n + 1 мест для разрезов выглядит так (| означает возможный разрез):
Рассмотрим набор из k разрезов. Между каждой парой соседних разрезов находится бинарная строка, составленная из типов ингредиентов. Ингредиенты перед первым разрезом и после последнего не учитываются. Поэтому всего будет ровно k - 1 бинарных строк. Каждая строка может быть прочитана как число в двоичной системе счисления. Пусть m — это максимальное число среди полученных. Если все полученные числа положительны, и среди них встречаются все числа от 1 до m, то такой набор разрезов считается корректным.
Например, пусть Покеблок имеет вид 101101001110 и мы сделали 5 разрезов:
Полученные 4 бинарных подстроки: 11, 010, 01 и 1, они соответствуют числам 3, 2, 1 и 1 соответственно. В данном случае m = 3, потому что это максимальное среди чисел. Все числа положительные, и встречаются все числа от 1 до m. Поэтому этот набор разрезов — корректный набор 5 разрезов.
Покемон типа k эволюционирует только если Покеблок разрезан набором из k разрезов. Возможно, существуют несколько наборов разрезов с одинаковым числом разрезов. Два корректных набора k разрезов считаются различными, если в одном наборе есть разрез, которого нет в другом наборе.
Пусть f(k) — число корректных наборов k разрезов. Найдите значение . Так как число s может быть большим, выведите остаток от деления s на 109 + 7.
Входные данные содержат две строки. Первая строка содержит число n (1 ≤ n ≤ 75) — длина Покеблока. Вторая строка содержит Покеблок — бинарную строку длину n.
Выведите единственное число — остаток от деления s на 109 + 7.
4
1011
10
2
10
1
В первом примере корректные наборы разрезов следующие:
Размер 2: |1|011, 1|01|1, 10|1|1, 101|1|.
Размер 3: |1|01|1, |10|1|1, 10|1|1|, 1|01|1|.
Размер 4: |10|1|1|, |1|01|1|.
Поэтому, f(2) = 4, f(3) = 4 и f(4) = 2. Значит, s = 10.
Во втором примере единственный корректный набор разрезов следующий:
Размер 2: |1|0.
Поэтому, f(2) = 1 и f(3) = 0. Значит s = 1.
Название |
---|