En un piso infinitamente grande, debes colocar un número infinito de baldosas.

Cada baldosa tiene un patrón de celdas cuadradas de tamaño $n \times n$. Cada celda de la baldosa tiene una tira de luz LED fijada a lo largo de sus bordes inferior e izquierdo, con diferentes colores que crean un patrón colorido.

El patrón en cada baldosa es exactamente el mismo. Al colocar las baldosas, pondremos un número infinito de ellas una al lado de la otra sin espacios, formando un patrón de tiras de luz infinitamente grande.

Hay $k$ colores diferentes disponibles, y debes elegir los colores correspondientes para un total de $2n^2$ tiras de luz en una baldosa, tras lo cual las demás baldosas replicarán automáticamente este esquema de coloración. Al colocar las baldosas, todas se pondrán en la misma dirección, lo que significa que pueden verse como una traslación directa de una sola baldosa unida a las demás sin rotación.

Mientras caminas por el piso, quieres saber cuántos esquemas esencialmente diferentes existen para colorear las baldosas. Dado que el piso es infinito y una persona puede mirar hacia diferentes direcciones (norte, sur, este, oeste) al observar las baldosas, dos esquemas se definen como esencialmente iguales si y solo si:

Al observar el plano infinito del piso creado por los dos esquemas, si existe una serie de traslaciones o rotaciones (excluyendo reflexiones) que pueda hacer que los colores de las tiras de luz en todas las posiciones del piso sean completamente idénticos, entonces estos dos esquemas se consideran esencialmente iguales.

Entrada

Hay múltiples casos de prueba en un solo archivo de entrada. La primera línea de la entrada contiene un solo entero positivo $T$ ($1 \le T \le 10$), que indica el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene dos enteros $n$ y $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), que representan el tamaño del patrón y el número de colores, respectivamente.

Salida

Para cada caso de prueba, imprime una sola línea con un único entero, que representa el número de esquemas esencialmente diferentes, módulo $10^9 + 7$.

Ejemplo

Entrada 1

3
1 2
2 2
114514 5201314

Salida 1

3
31
377726028

Nota

La siguiente imagen muestra 19 esquemas de construcción para $n = k = 2$ (para ilustrar mejor el efecto del embaldosado, cada imagen muestra 9 baldosas dispuestas en un patrón de $3 \times 3$, con luces LED en colores oscuro y claro). Al intercambiar los colores oscuro y claro de los primeros 12 esquemas, se pueden obtener otros 12 esquemas, resultando en un total de 31 esquemas.