Äärettömän suurelle lattialle täytyy asettaa ääretön määrä laattoja.

Jokaisessa laatassa on $n \times n$ -kokoinen neliöruudukkokuvio. Laatan jokaisen ruudun ala- ja vasempaan reunaan on kiinnitetty LED-valonauha, ja eri värit muodostavat värikkään kuvion.

Kuvio on jokaisessa laatassa täsmälleen sama. Laattoja asetettaessa ääretön määrä laattoja sijoitetaan saumattomasti vierekkäin, jolloin muodostuu äärettömän suuri valonauhakuvio.

Käytettävissä on $k$ eri väriä, ja sinun tulee valita värit yhden laatan yhteensä $2n^2$ valonauhalle, minkä jälkeen muut laatat toistavat automaattisesti tämän värityksen. Laattoja asetettaessa kaikki laatat asetetaan samaan suuntaan, eli ne voidaan ajatella yhden laatan suorina yhdensuuntaissiirtoina, jotka on liitetty yhteen ilman kiertoa.

Kävellessäsi lattialla haluat tietää, kuinka monta olennaisesti erilaista tapaa laattojen värittämiseen on olemassa. Koska lattia on ääretön ja laattoja tarkasteleva henkilö voi katsoa eri ilmansuuntiin (pohjoinen, etelä, itä, länsi), kaksi väritystä määritellään olennaisesti samoiksi, jos ja vain jos:

Kun tarkastellaan kahden värityksen muodostamaa ääretöntä lattiatasoa, on olemassa sarja yhdensuuntaissiirtoja tai kiertoja (ilman peilauksia), joilla valonauhojen värit lattian kaikissa kohdissa saadaan täysin samoiksi — tällöin näitä kahta väritystä pidetään olennaisesti samoina.

Syöte

Yhdessä testitiedostossa on useita testitapauksia. Syötteen ensimmäisellä rivillä on yksi positiivinen kokonaisluku $T$ ($1 \le T \le 10$), joka ilmaisee testitapausten määrän.

Jokaisessa testitapauksessa:

• Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), jotka ilmaisevat kuvion koon ja värien määrän.

Tuloste

Tulosta jokaista testitapausta kohden yhdelle riville yksi kokonaisluku, joka ilmaisee olennaisesti erilaisten väritysten määrän modulo $10^9 + 7$.

Esimerkki

Syöte 1

3
1 2
2 2
114514 5201314

Tuloste 1

3
31
377726028

Huomautus

Seuraava kuva esittää 19 rakennetta tapauksessa $n = k = 2$ (laatoitusvaikutelman havainnollistamiseksi jokaisessa kuvassa näkyy 9 laattaa $3 \times 3$ -muodossa, ja LED-valoja on tummina ja vaaleina). Vaihtamalla ensimmäisten 12 rakenteen tummat ja vaaleat värit keskenään saadaan vielä 12 rakennetta, eli yhteensä 31 rakennetta.