Sur un sol infiniment grand, vous devez poser un nombre infini de carreaux.

Chaque carreau possède un motif de grille carrée de taille $n \times n$. Chaque cellule de la grille du carreau a une bande lumineuse LED fixée le long de ses bords inférieur et gauche, avec différentes couleurs qui créent un motif coloré.

Le motif sur chaque carreau est exactement le même. Lors de la pose des carreaux, nous placerons un nombre infini de carreaux côte à côte sans jointure, formant un motif de bandes lumineuses infiniment grand.

Il y a $k$ couleurs différentes disponibles, et vous devez choisir les couleurs correspondantes pour un total de $2n^2$ bandes lumineuses sur un carreau, après quoi les autres carreaux reproduiront automatiquement ce schéma de coloration. Lors de la pose, tous les carreaux seront posés dans la même direction, ce qui signifie qu'ils peuvent être vus comme une simple translation d'un carreau assemblé aux autres sans rotation.

En marchant sur le sol, vous voulez savoir combien il existe de schémas de coloration essentiellement différents. Comme le sol est infini et qu'une personne peut faire face à différentes directions (nord, sud, est, ouest) en observant les carreaux, deux schémas sont définis comme essentiellement identiques si et seulement si :

En observant le plan infini du sol créé par les deux schémas, s'il existe une série de translations ou de rotations (à l'exclusion des réflexions) permettant de rendre les couleurs des bandes lumineuses en toutes les positions du sol complètement identiques, alors ces deux schémas sont considérés comme essentiellement identiques.

Entrée

Il y a plusieurs cas de test dans un seul fichier d'entrée. La première ligne de l'entrée contient un entier positif $T$ ($1 \le T \le 10$), indiquant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient deux entiers $n$ et $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), représentant respectivement la taille du motif et le nombre de couleurs.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier, représentant le nombre de schémas essentiellement différents, modulo $10^9 + 7$.

Exemple

Entrée 1

3
1 2
2 2
114514 5201314

Sortie 1

3
31
377726028

Note

L'image suivante montre 19 schémas de construction pour $n = k = 2$ (pour mieux illustrer l'effet du carrelage, chaque image montre 9 carreaux disposés selon un motif $3 \times 3$, avec des LED disponibles en couleurs foncée et claire). En échangeant les couleurs foncée et claire des 12 premiers schémas, 12 autres schémas peuvent être obtenus, soit un total de 31 schémas.