D. Секрет фестиваля раскрыт
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Руководители школ очарованы эволюционированием, произошедшим в специальном лагере. Поэтому им было интересно узнать секрет эволюционирования.

Организаторы лагеря дали руководителям Покеблок — последовательность из 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 мест для разрезов выглядит так (| означает возможный разрез):

| b0 | b1 | b2 | ... | bn - 2 | bn - 1 |

Рассмотрим набор из k разрезов. Между каждой парой соседних разрезов находится бинарная строка, составленная из типов ингредиентов. Ингредиенты перед первым разрезом и после последнего не учитываются. Поэтому всего будет ровно k - 1 бинарных строк. Каждая строка может быть прочитана как число в двоичной системе счисления. Пусть m — это максимальное число среди полученных. Если все полученные числа положительны, и среди них встречаются все числа от 1 до m, то такой набор разрезов считается корректным.

Например, пусть Покеблок имеет вид 101101001110 и мы сделали 5 разрезов:

10 | 11 | 010 | 01 | 1 | 10

Полученные 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.