Bessie ha una striscia di tela lunga $N$ unità ($1 \leq N \leq 10^6$) e vuole dipingerla, ma non ha potuto procurarsi pennelli. Al loro posto ha $M$ timbri di gomma di colori diversi ($1 \leq M \leq 10^6$), ognuno largo $K$ unità ($1 \leq K \leq 10^6$). Stupita dalle possibilità, vuole sapere esattamente quante immagini diverse può creare timbrando in un certo ordine.
Un timbro deve allinearsi esattamente a $K$ unità vicine della tela. Non può oltrepassarne le estremità né coprire frazioni di unità. Colora le $K$ unità coperte con il proprio colore. Ogni timbro può essere usato molte volte, una o mai. Ma quando Bessie finisce, ogni unità deve essere stata colorata almeno una volta.
Aiuta Bessie a trovare il numero di immagini diverse modulo $10^9 + 7$. Immagini di aspetto identico ottenute con sequenze diverse contano come la stessa.
Input
L’unica riga contiene tre interi $N$, $M$ e $K$. È garantito $K \leq N$.
Output
Un intero: il numero di immagini possibili modulo $10^9 + 7$.
Esempi
Input 1
3 2 2
Output 1
6
Nota
Se i due timbri hanno colori A e B, le immagini possibili sono AAA, AAB, ABB, BAA, BBA e BBB.
Sottoproblemi
In almeno il $75\%$ dei casi di input, $N,K \leq 10^3$.
Autore del problema: Dhruv Rohatgi