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

Назовем две строки $$$a$$$ и $$$b$$$ равными, если можно получить строку $$$b$$$ циклическим сдвигом строки $$$a$$$. Например, строки 0100110 и 1100100 — равны, а строки 1010 и 1100 — не равны.

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

За одну операцию вы можете заменить один 0 на 1.

Посчитайте количество уникальных строк, которые вы можете получить, используя не более $$$k$$$ операций. Поскольку ответ может быть слишком большим, выведите его по модулю $$$10^9 + 7$$$.

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

Первая и единственная строка содержит три целых числа $$$n$$$, $$$c$$$ и $$$k$$$ ($$$1 \le n \le 3000$$$; $$$1 \le c \le n$$$; $$$0 \le k \le n - c$$$) — длина строки $$$s$$$, длина префикса из 1 и максимальное количество операций.

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

Выведите одно целое число — количество уникальных строк, которые вы можете получить, выполнив не более $$$k$$$ операций, по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
1 1 0
Выходные данные
1
Входные данные
3 1 2
Выходные данные
3
Входные данные
5 1 1
Выходные данные
3
Входные данные
6 2 2
Выходные данные
7
Входные данные
24 3 11
Выходные данные
498062
Примечание

В первом тесте возможная строка: 1.

Во втором тесте возможные строки: 100, 110 и 111. Строка 101 равна 110, поэтому мы ее не учитываем.

В третьем тесте возможные строки: 10000, 11000, 10100. Строка 10010 равна 10100, а 10001 равна 11000.