Игорь и Ира решили определить главного в семье, для этого они проведут турнир по стрельбе из лука. Турнир проходит по простым правилам: каждый из участников делает по $$$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
