Bessie se ha encontrado en posesión de un lienzo de ~N~ unidades de largo ~(1 \leq N \leq 10^6)~, y ella intenta pintarlo.Sin embargo, ella no ha podido conseguir pinceles. En vez de esto ella tiene ~M~ sellos de goma de colores diferentes ~(1 \leq M \leq 10^6)~, cada sellos de ~K~ unidades de ancho ~(1 \leq K \leq 10^6)~. Desconcertada por las posibilidades que están delante de ella, ella quiere saber exactamente cuántas pinturas podría crear potencialmente, estampando con sus sellos en algún orden el lienzo.

Para usar un sello, primero debe ser alineado con exactamente ~K~ unidades vecinas en el lienzo. El sello no puede extenderse más allá de los extremos del lienzo, ni puede cubrir fracciones de unidades. Una vez puesto, el sello pinta las ~K~ unidades cubiertas con su color. Cualquier sello puede ser usado varias veces, o ninguna vez en total. Pero cuando Bessie termina, cada unidad de lienzo debe haber sido pintada al menos una vez.

Ayude a Bessie a encontrar el número de pinturas diferentes que ella podría pintar, modulo ~10^9+7~. Dos pinturas que se vean iguales pero que hayan sido pintada por diferentes sencuencias de operaciones de estampado serán consideradas la misma.

Para al menos 75% de los casos de entrada, ~( N,K \leq 1000 )~.

Entrada

La primera y única línea de la entrada contiene tres enteros ~N~ , ~M~ y ~K~. Se garantiza que ~K \leq N~.

Salida

Un solo entero: el número de posibles pinturas, modulo ~10^9+7~.

Ejemplo de Entrada

3 2 2

Ejemplo de Salida

6

Si los dos sellos tienen colores A y B, las posibles pinturas son AAA, AAB, ABB, BAA, BBA, y BBB.