Назовем две строки \(a\) и \(b\) равными, если можно получить строку \(b\) циклическим сдвигом строки \(a\). Например, строки 0100110 и 1100100 — равны, а строки 1010 и 1100 — не равны.
Вам задана бинарная строка \(s\) длины \(n\). Каждый из ее первых \(c\) символов — это 1, а каждый из последних \(n - c\) символов — это 0.
За одну операцию вы можете заменить один 0 на 1.
Посчитайте количество уникальных строк, которые вы можете получить, используя не более \(k\) операций. Поскольку ответ может быть слишком большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Выведите одно целое число — количество уникальных строк, которые вы можете получить, выполнив не более \(k\) операций, по модулю \(10^9 + 7\).
Примечание
В первом тесте возможная строка: 1.
Во втором тесте возможные строки: 100, 110 и 111. Строка 101 равна 110, поэтому мы ее не учитываем.
В третьем тесте возможные строки: 10000, 11000, 10100. Строка 10010 равна 10100, а 10001 равна 11000.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 0
|
1
|
|
2
|
3 1 2
|
3
|
|
3
|
5 1 1
|
3
|
|
4
|
6 2 2
|
7
|
|
5
|
24 3 11
|
498062
|