Á óendanlega stóru gólfi þarftu að leggja óendanlega margar flísar.

Hver flís er með ferhyrnt reitamynstur af stærð $n \times n$. Hver reitur á flísinni er með LED-ljósaræmu festa meðfram neðri og vinstri brún sinni, með mismunandi litum sem skapa litríkt mynstur.

Mynstrið á hverri flís er nákvæmlega eins. Þegar flísarnar eru lagðar röðum við óendanlega mörgum flísum þétt saman hlið við hlið, þannig að þær mynda óendanlega stórt ljósaræmumynstur.

Það eru $k$ mismunandi litir í boði og þú þarft að velja samsvarandi liti fyrir samtals $2n^2$ ljósaræmur á einni flís, og eftir það munu hinar flísarnar sjálfkrafa endurtaka þessa litasamsetningu. Þegar flísarnar eru lagðar snúa þær allar í sömu átt, sem þýðir að líta má á þær sem beina hliðrun á einni flís sem síðan er skeytt saman án snúnings.

Þegar þú gengur um gólfið viltu vita hversu margar í eðli sínu ólíkar leiðir eru til að lita flísarnar. Þar sem gólfið er óendanlegt og manneskja getur horft í mismunandi áttir (norður, suður, austur, vestur) þegar hún skoðar flísarnar, eru tvær leiðir skilgreindar sem í eðli sínu eins ef og aðeins ef:

Þegar óendanlegi gólfflöturinn sem myndast af leiðunum tveimur er skoðaður, ef til er runa af hliðrunum eða snúningum (speglanir undanskildar) sem getur gert liti ljósaræmanna á öllum stöðum á gólfinu alveg eins, þá teljast þessar tvær leiðir vera í eðli sínu eins.

Inntak

Það eru mörg prófunartilvik í einni inntaksskrá. Fyrsta línan í inntakinu inniheldur eina jákvæða heiltölu $T$ ($1 \le T \le 10$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), sem tákna stærð mynstursins og fjölda lita.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með einni heiltölu sem táknar fjölda í eðli sínu ólíkra leiða, modulo $10^9 + 7$.

Dæmi

Inntak 1

3
1 2
2 2
114514 5201314

Úttak 1

3
31
377726028

Skýring

Eftirfarandi mynd sýnir 19 gerðir fyrir $n = k = 2$ (til að sýna flísalögnina betur sýnir hver mynd 9 flísar sem raðað er í $3 \times 3$ mynstur, þar sem LED-ljósin eru í dökkum og ljósum lit). Með því að víxla dökka og ljósa litnum í fyrstu 12 gerðunum má fá 12 gerðir í viðbót, sem gefur samtals 31 gerð.