Bessie possède une bande de toile longue de $N$ unités ($1 \leq N \leq 10^6$) qu’elle veut peindre. Elle n’a cependant pas trouvé de pinceaux. À leur place, elle a $M$ tampons en caoutchouc de couleurs différentes ($1 \leq M \leq 10^6$), chacun large de $K$ unités ($1 \leq K \leq 10^6$). Émerveillée par les possibilités, elle veut savoir exactement combien de peintures différentes elle peut créer en appliquant les tampons dans un certain ordre.

Un tampon doit être aligné exactement sur $K$ unités voisines de toile. Il ne peut dépasser les extrémités ni couvrir des fractions d’unités. Il colore les $K$ unités couvertes avec sa couleur. Chaque tampon peut être utilisé plusieurs fois, une fois ou jamais. Mais quand Bessie termine, chaque unité doit avoir été peinte au moins une fois.

Aidez Bessie à trouver le nombre de peintures différentes modulo $10^9 + 7$. Deux peintures visuellement identiques obtenues par des séquences différentes sont comptées comme une seule.

Entrée

L’unique ligne contient trois entiers $N$, $M$ et $K$. Il est garanti que $K \leq N$.

Sortie

Un entier : le nombre de peintures possibles modulo $10^9 + 7$.

Exemples

Entrée 1

3 2 2

Sortie 1

6

Remarque

Avec deux tampons de couleurs A et B, les peintures possibles sont AAA, AAB, ABB, BAA, BBA et BBB.

Sous-tâches

Pour au moins $75\%$ des cas d’entrée, $N,K \leq 10^3$.

Auteur du problème : Dhruv Rohatgi