Tu tarea consiste en contar el número de secuencias de longitud ~n~ donde cada elemento es un entero entre ~1 \dots k~ y cada entero entre ~1 \dots k~ aparece al menos una vez en la secuencia.

Por ejemplo, cuando ~n=6~ y ~k=4~, algunas secuencias válidas son ~[1,3,1,4,3,2]~ y ~[2,2,1,3,4,2]~.

Entrada

La única línea de entrada contiene dos enteros, ~n~ y ~k~.

Salida

Imprime un entero: el número de secuencias módulo ~10^9+7~.

Restricciones

• ~1 \leq k \leq n \leq 10^6~

Ejemplo de Entrada

6 4

Ejemplo de Salida

1560