På et uendelig stort gulv skal du legge et uendelig antall fliser.

Hver flis har et rutenettmønster av kvadratiske celler med størrelse $n \times n$. Hver celle på flisen har en LED-lyslist festet langs sin nederste og venstre kant, med forskjellige farger som skaper et fargerikt mønster.

Mønsteret på hver flis er nøyaktig det samme. Når vi legger flisene, plasserer vi et uendelig antall fliser sømløst ved siden av hverandre, slik at de danner et uendelig stort lyslistmønster.

Det er $k$ forskjellige farger tilgjengelig, og du må velge tilsvarende farger for totalt $2n^2$ lyslister på én flis, hvorpå de andre flisene automatisk vil kopiere dette fargeskjemaet. Når flisene legges, vil alle flisene bli lagt i samme retning, noe som betyr at de kan betraktes som en direkte parallellforskyvning av én flis som deretter settes sammen uten rotasjon.

Mens du går på gulvet, vil du vite hvor mange vesentlig forskjellige skjemaer det finnes for å fargelegge flisene. Siden gulvet er uendelig, og en person kan se i forskjellige retninger (nord, sør, øst, vest) når man observerer flisene, defineres to skjemaer som vesentlig like hvis og bare hvis:

Når man observerer det uendelige gulvplanet som skapes av de to skjemaene, hvis det finnes en rekke parallellforskyvninger eller rotasjoner (unntatt speilinger) som kan gjøre fargene på lyslistene på alle posisjoner på gulvet fullstendig identiske, så regnes disse to skjemaene som vesentlig like.

Inndata

Det er flere testtilfeller i én enkelt testfil. Den første linjen i inndataene inneholder et positivt heltall $T$ ($1 \le T \le 10$), som angir antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder to heltall $n$ og $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), som representerer henholdsvis størrelsen på mønsteret og antallet farger.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje med ett heltall, som representerer antallet vesentlig forskjellige skjemaer, modulo $10^9 + 7$.

Eksempel

Inndata 1

3
1 2
2 2
114514 5201314

Utdata 1

3
31
377726028

Forklaring

Følgende bilde viser 19 konstruksjonsskjemaer for $n = k = 2$ (for å illustrere flisleggingseffekten bedre, viser hvert bilde 9 fliserordnet i et $3 \times 3$-mønster, med LED-lys i mørk og lys farge). Ved å bytte om på den mørke og lyse fargen i de første 12 skjemaene, kan man få ytterligere 12 skjemaer, noe som gir totalt 31 skjemaer.