Patrón#13075

Patrón

1 segundo
256 megabytes

Olenka está fabricando un sello para estampar un patrón en una cinta. Un sello es una tira de celdas, cada una de las cuales está pintada de uno de colores. Denotemos los colores de las celdas de izquierda a derecha como w_1, w_2, \ldots, w_n (1 \le w_i \le k).

Para que las impresiones en la cinta no se puedan confundir, Olenka necesita un sello exitoso. Un sello se llama exitoso si ningún prefijo suyo está pintado igual que el sufijo de la misma longitud. Es decir, para cada desde hasta n - 1 las primeras celdas difieren de las últimas :

w_1 w_2 \ldots w_l \ne w_{n-l+1} w_{n-l+2} \ldots w_n.

Un sello formado por una sola celda siempre es exitoso.

Por ejemplo, para k = 3 los sellos , y son exitosos, mientras que los sellos (l = 1), (l = 2) y (l = 1, 2, 3) no lo son.

Se te dan consultas. Para cada consulta, cuenta la cantidad de sellos exitosos formados por celdas pintadas con colores. Como las respuestas pueden ser muy grandes, imprímelas módulo 10^9 + 7.

Entrada

La primera línea contiene un único entero (1 \le t \le 10^5) — la cantidad de consultas.

Cada una de las siguientes líneas contiene dos enteros y (1 \le n \le 10^6, 1 \le k \le 10^9) — la cantidad de celdas del sello y la cantidad de colores.

Se garantiza que la suma de sobre todas las consultas no supera 10^6.

Salida

Para cada consulta, imprime en una línea separada la cantidad de sellos exitosos formados por celdas pintadas con colores, módulo 10^9 + 7.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Nota

En el primer ejemplo:

  • Para n = 1 los sellos son exitosos.

  • Para n = 2, k = 3 un sello es exitoso si y solo si sus dos celdas tienen colores distintos: 3 \cdot 2 = 6 sellos.

  • Para n = 3, k = 2 los sellos exitosos son , , y .

  • Para n = 4, k = 2 los sellos exitosos son , , , , y . Por ejemplo, el sello no es exitoso porque sus dos primeras celdas están pintadas igual que sus dos últimas, y el sello no es exitoso porque empieza y termina con el color .