Bessie tiene una tira de lienzo de $N$ unidades ($1 \leq N \leq 10^6$) y quiere pintarla, pero no ha conseguido pinceles. En su lugar tiene $M$ sellos de goma de colores distintos ($1 \leq M \leq 10^6$), cada uno de $K$ unidades de ancho ($1 \leq K \leq 10^6$). Asombrada por las posibilidades, quiere saber exactamente cuántas pinturas distintas puede crear estampando los sellos en algún orden.
El sello debe alinearse con exactamente $K$ unidades contiguas del lienzo. No puede sobresalir de los extremos ni cubrir fracciones de unidades. Pinta las $K$ unidades cubiertas de su color. Cada sello puede usarse muchas veces, una o ninguna. Pero al terminar Bessie, toda unidad debe haberse pintado al menos una vez.
Ayuda a Bessie a hallar el número de pinturas distintas módulo $10^9 + 7$. Dos pinturas de aspecto idéntico obtenidas con secuencias distintas se cuentan como la misma.
Entrada
La única línea contiene tres enteros $N$, $M$ y $K$. Se garantiza $K \leq N$.
Salida
Un entero: el número de pinturas posibles módulo $10^9 + 7$.
Ejemplos
Entrada 1
3 2 2
Salida 1
6
Nota
Si los dos sellos tienen colores A y B, las pinturas posibles son AAA, AAB, ABB, BAA, BBA y BBB.
Subtareas
En al menos el $75\%$ de los casos de entrada, $N,K \leq 10^3$.
Autor del problema: Dhruv Rohatgi