Дана бинарная строка 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.
Выходные данные
Выведите одно целое число — сумма стоимостей всех подпоследовательностей строки F(x) по модулю 109 + 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4
11
|
14
|
|
2
|
10 100
1010101010
|
553403224
|