På ett oändligt stort golv ska du lägga ett oändligt antal plattor.

Varje platta har ett rutnätsmönster av kvadratiska celler med storleken $n \times n$. Varje cell på plattan har en LED-ljuslist fäst längs sin nedre och vänstra kant, med olika färger som skapar ett färggrant mönster.

Mönstret på varje platta är exakt detsamma. När vi lägger plattorna placerar vi ett oändligt antal plattor sömlöst bredvid varandra, vilket bildar ett oändligt stort ljuslistmönster.

Det finns $k$ olika färger tillgängliga, och du måste välja motsvarande färger för totalt $2n^2$ ljuslister på en platta, varefter de andra plattorna automatiskt kopierar detta färgschema. När plattorna läggs kommer alla plattor att läggas i samma riktning, vilket innebär att de kan ses som en direkt parallellförflyttning av en platta som sedan fogas samman utan rotation.

När du går på golvet vill du veta hur många väsentligen olika scheman det finns för att färglägga plattorna. Eftersom golvet är oändligt och en person kan titta i olika riktningar (norr, söder, öster, väster) när man betraktar plattorna, definieras två scheman som väsentligen lika om och endast om:

När man betraktar det oändliga golvplanet som skapas av de tvåรschemana, om det finns en följd av parallellförflyttningar eller rotationer (exklusive speglingar) som kan få färgerna på ljuslisterna på alla positioner på golvet att bli helt identiska, då betraktas dessa två scheman som väsentligen lika.

Indata

Det finns flera testfall i en enda testfil. Den första raden i indatan innehåller ett positivt heltal $T$ ($1 \le T \le 10$), som anger antalet testfall.

För varje testfall:

• Den första raden innehåller två heltal $n$ och $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), som representerar storleken på mönstret respektive antalet färger.

Utdata

För varje testfall, skriv ut en enda rad med ett heltal som representerar antalet väsentligen olika scheman, modulo $10^9 + 7$.

Exempel

Indata 1

3
1 2
2 2
114514 5201314

Utdata 1

3
31
377726028

Förklaring

Följande bild visar 19 konstruktionsscheman för $n = k = 2$ (för att bättre illustrera plattsättningseffekten visar varje bild 9 plattor ordnade i ett $3 \times 3$-mönster, med LED-lister i mörk och ljus färg). Genom att byta plats på den mörka och ljusa färgen i de första 12 schemana kan ytterligare 12 scheman erhållas, vilket ger totalt 31 scheman.