Задача H. Нерассудительность ≡

Условие

У вас есть друг Петя, которому вы дали k рублей и отправили его в магазин купить круп, чтобы приготовить ужин. Вы сказали ему сколько и чего купить, но у него, конечно же, сразу всё вылетело из головы. Однако Петя - человек гордый, поэтому звонить и переспрашивать не будет. Он поступит нерассудительно - купит крупы наугад.

В магазине все крупы продаются только пакетами по 1кг и стоят одинаково.

Вы знаете об этой особенности Пети, и хотите рассчитать вероятность, что он купит именно то, что вы и попросили. Но для этого надо рассчитать сколько различных покупок может сделать Петя.

Две покупки являются различными, если существует такая крупа, что ее количество в первой покупке отличается от количества во второй покупке.

Петя отличается силой, в отличие от памяти, поэтому он может унести сколько угодно килограмм.

Петя может как купить на все деньги крупы одного вида, так и не купить круп вовсе (прийти в магазин просто так).

Формат входных данных

Во входной строке три целый числа: n, k и m - количество видов круп, количество денег у Пети и стоимость одного килограмма. (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ k ≤ 10⁵)

Формат выходных данных

Выведите одно целое число - количество различных покупок, которые может сделать Петя.

Так как ответ может оказаться слишком большим, выведете его по модулю 10⁹ + 7

Примеры тестов

1 2 1

3

2 4 2

6