Bessie ma pas płótna długości $N$ jednostek ($1 \leq N \leq 10^6$) i chce go pomalować, ale nie zdobyła pędzli. Zamiast nich ma $M$ gumowych stempli różnych kolorów ($1 \leq M \leq 10^6$), każdy szerokości $K$ jednostek ($1 \leq K \leq 10^6$). Zdumiona możliwościami chce dokładnie wiedzieć, ile różnych obrazów może stworzyć, stemplując w pewnej kolejności.

Stempel trzeba dopasować dokładnie do $K$ sąsiednich jednostek płótna. Nie może wystawać poza końce ani pokrywać ułamków jednostek. Maluje $K$ pokrytych jednostek swoim kolorem. Każdy stempel można użyć wiele razy, raz albo wcale. Gdy Bessie skończy, każda jednostka musi być jednak pomalowana co najmniej raz.

Pomóż Bessie znaleźć liczbę różnych obrazów modulo $10^9 + 7$. Obrazy wyglądające identycznie, lecz otrzymane różnymi sekwencjami stempli, liczą się jako ten sam.

Wejście

Jedyny wiersz zawiera trzy liczby całkowite $N$, $M$ i $K$. Gwarantowane jest $K \leq N$.

Wyjście

Jedna liczba całkowita: liczba możliwych obrazów modulo $10^9 + 7$.

Przykład

Wejście 1

3 2 2

Wyjście 1

6

Uwagi

Jeśli dwa stemple mają kolory A i B, możliwe obrazy to AAA, AAB, ABB, BAA, BBA i BBB.

Podzadania

W co najmniej $75\%$ przypadków wejściowych $N,K \leq 10^3$.

Autor zadania: Dhruv Rohatgi