F. Фибоначчиевы подпоследовательности
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана бинарная строка s (каждый символ в строке равен либо 0, либо 1).

Определим стоимость строки t как количество вхождений s в t. Например, если s равна 11 и t равна 111011, то стоимость t равна 3.

Определим также фибоначчиевы строки следующим образом:

  • F(0) равна 0;
  • F(1) равна 1;
  • F(i) = F(i - 1) + F(i - 2) для i > 1, где  +  означает конкатенацию двух строк.

Ваша задача — посчитать сумму стоимостей всех подпоследовательностей строки F(x). Так как ответ может быть очень большим, выведите его по модулю 109 + 7.

Входные данные

В первой строке записаны два целых числа n и x (1 ≤ n ≤ 100, 0 ≤ x ≤ 100) — длина строки s и номер требуемой фибоначчиевой строки, соответственно.

Во второй строке содержится s — строка, состоящая из n символов. Каждый из этих символов равен либо 0, либо 1.

Выходные данные

Выведите одно целое число — сумма стоимостей всех подпоследовательностей строки F(x) по модулю 109 + 7.

Примеры
Входные данные
2 4
11
Выходные данные
14
Входные данные
10 100
1010101010
Выходные данные
553403224