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

Игорь и Ира решили определить главного в семье, для этого они проведут турнир по стрельбе из лука. Турнир проходит по простым правилам: каждый из участников делает по $$$n$$$ выстрелов (сначала все свои выстрелы делает первый участник, потом второй). Мишень — круг, состоящий из $$$k$$$ колец, за попадание в каждое из которых начисляется от $$$1$$$ до $$$k$$$ очков. Главным в семье будет тот, кто сможет набрать большее количество очков.

Игорь уже произвел свои $$$n$$$ выстрелов и набрал $$$p$$$ очков, теперь очередь Иры. Она уже приноровилась к стрельбе из лука, и теперь всегда попадает в мишень, в отличие от Игоря. При выстреле Ира попадает в каждое кольцо с одинаковой вероятностью.

Помогите Ире определить количество выигрышных комбинаций из $$$n$$$ выстрелов.

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

В единственной строке записаны три целых числа $$$n$$$, $$$k$$$, $$$p$$$ $$$(1\leq n, k\leq 300, 0 \le p\leq k\cdot n)$$$ — количество выстрелов, количество колец на мишени и количество очков, набранных Игорем.

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

В единственной строке выведите число — количество комбинаций из $$$n$$$ выстрелов Иры в мишень, таких, что сумма набранных очков будет больше, чем $$$p$$$.

Выведите ответ по модулю 1000000007$$$(10^9+7)$$$.

Примеры
Входные данные
3 3 7
Выходные данные
4
Входные данные
5 5 6
Выходные данные
3119
Примечание

В первом тесте существуют следующие комбинации попаданий Ирой в мишень, при которых она набирает очков больше, чем Игорь.

$$$[2,3,3]$$$ сумма очков: 8

$$$[3,2,3]$$$ сумма очков: 8

$$$[3,3,2]$$$ сумма очков: 8

$$$[3,3,3]$$$ сумма очков: 9