У Bessie есть полоска холста длиной $N$ единиц ($1 \leq N \leq 10^6$), которую она хочет раскрасить. Но кистей нет. Вместо них у неё $M$ резиновых штампов разных цветов ($1 \leq M \leq 10^6$), каждый шириной $K$ единиц ($1 \leq K \leq 10^6$). Поражённая возможностями, она хочет точно знать, сколько разных картин можно получить, прикладывая штампы в некотором порядке.

Штамп совмещают ровно с $K$ соседними единицами холста. Он не может выходить за края или покрывать части единиц. Он окрашивает все $K$ покрытые единицы своим цветом. Каждый штамп можно использовать многократно, один раз или ни разу. Но к завершению работы Bessie каждая единица должна быть окрашена хотя бы раз.

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

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

Единственная строка содержит три целых числа $N$, $M$ и $K$. Гарантируется $K \leq N$.

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

Одно целое число: число возможных картин по модулю $10^9 + 7$.

Примеры

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

3 2 2

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

6

Примечание

Если цвета двух штампов A и B, возможны AAA, AAB, ABB, BAA, BBA и BBB.

Подзадачи

Не менее чем в $75\%$ входных случаев $N,K \leq 10^3$.

Автор задачи: Dhruv Rohatgi