Su un pavimento infinitamente grande, devi posare un numero infinito di piastrelle.

Ogni piastrella ha un motivo a griglia quadrata di dimensione $n \times n$. Ogni cella della griglia della piastrella ha una striscia luminosa a LED fissata lungo il bordo inferiore e quello sinistro, con colori diversi che creano un motivo colorato.

Il motivo su ogni piastrella è esattamente lo stesso. Durante la posa delle piastrelle, posizioneremo un numero infinito di piastrelle l'una accanto all'altra senza interruzioni, formando un motivo di strisce luminose infinitamente grande.

Sono disponibili $k$ colori diversi e devi scegliere i colori corrispondenti per un totale di $2n^2$ strisce luminose su una piastrella, dopodiché le altre piastrelle replicheranno automaticamente questo schema di colorazione. Durante la posa, tutte le piastrelle verranno posate nella stessa direzione, il che significa che possono essere viste come una traslazione diretta di una singola piastrella poi unita alle altre senza rotazione.

Mentre cammini sul pavimento, vuoi sapere quanti schemi essenzialmente diversi esistono per colorare le piastrelle. Poiché il pavimento è infinito e una persona può guardare in direzioni diverse (nord, sud, est, ovest) osservando le piastrelle, due schemi sono definiti essenzialmente uguali se e solo se:

Osservando il piano infinito del pavimento creato dai due schemi, se esiste una serie di traslazioni o rotazioni (escluse le riflessioni) in grado di rendere i colori delle strisce luminose in tutte le posizioni sul pavimento completamente identici, allora questi due schemi sono considerati essenzialmente uguali.

Input

Ci sono più casi di test in un singolo file di input. La prima riga dell'input contiene un singolo intero positivo $T$ ($1 \le T \le 10$), che indica il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene due interi $n$ e $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), che rappresentano rispettivamente la dimensione del motivo e il numero di colori.

Output

Per ciascun caso di test, stampa una singola riga con un singolo intero, che rappresenta il numero di schemi essenzialmente diversi, modulo $10^9 + 7$.

Esempio

Input 1

3
1 2
2 2
114514 5201314

Output 1

3
31
377726028

Note

L'immagine seguente mostra 19 schemi di costruzione per $n = k = 2$ (per illustrare meglio l'effetto della piastrellatura, ogni immagine mostra 9 piastrelle disposte secondo uno schema $3 \times 3$, con LED disponibili in colore scuro e chiaro). Scambiando i colori scuro e chiaro dei primi 12 schemi, si possono ottenere altri 12 schemi, per un totale di 31 schemi.