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

Организаторы лагеря дали руководителям Покеблок — последовательность из n ингредиентов. Каждый ингредиент имеет тип 0 или 1. Организаторы сказали руководителям, что чтобы покемон типа k (k ≥ 2) эволюционировал, необходимо сделать k разрезов Покеблока, получая меньшие блоки.

Пусть Покеблок это последовательность b₀b₁b₂... b_n - 1. Разрезы можно делать в n + 1 местах, то есть до b₀, между b₀ и b₁, между b₁ и b₂, ..., между b_n - 2 и b_n - 1, и после b_n - 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 на 10⁹ + 7.