| Автор: | Артем Завгороднев | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
У вас есть друг Петя, которому вы дали k рублей и отправили его в магазин купить круп, чтобы приготовить ужин. Вы сказали ему сколько и чего купить, но у него, конечно же, сразу всё вылетело из головы. Однако Петя - человек гордый, поэтому звонить и переспрашивать не будет. Он поступит нерассудительно - купит крупы наугад.
В магазине все крупы продаются только пакетами по 1кг и стоят одинаково.
Вы знаете об этой особенности Пети, и хотите рассчитать вероятность, что он купит именно то, что вы и попросили. Но для этого надо рассчитать сколько различных покупок может сделать Петя.
Две покупки являются различными, если существует такая крупа, что ее количество в первой покупке отличается от количества во второй покупке.
Петя отличается силой, в отличие от памяти, поэтому он может унести сколько угодно килограмм.
Петя может как купить на все деньги крупы одного вида, так и не купить круп вовсе (прийти в магазин просто так).
Во входной строке три целый числа: n, k и m - количество видов круп, количество денег у Пети и стоимость одного килограмма. (1 ≤ n ≤ 105, 1 ≤ m ≤ k ≤ 105)
Выведите одно целое число - количество различных покупок, которые может сделать Петя.
Так как ответ может оказаться слишком большим, выведете его по модулю 109 + 7
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|