Tu tarea consiste en contar el número de collares diferentes que constan de ~n~ perlas, cada una con ~m~ colores posibles.

Se considera que dos collares son diferentes si no es posible rotar uno de ellos para que se vean iguales.

Entrada

La única línea de entrada tiene dos números, ~n~ y ~m~: el número de perlas y colores.

Salida

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

Restricciones

• ~1 \leq n, m \leq 10^6~

Ejemplo de Entrada

4 3

Ejemplo de Salida

24