Шексіз үлкен еденге шексіз көп плитка төсеу керек.

Әрбір плиткада өлшемі $n \times n$ болатын шаршы тор үлгісі бар. Плитканың әрбір тор ұяшығының төменгі және сол жақ шекараларының бойымен түрлі-түсті өрнек жасайтын әртүрлі түсті LED жарық диодты жолағы бекітілген.

Әрбір плиткадағы өрнек бір-бірімен дәлме-дәл бірдей. Плиткаларды төсеген кезде біз шексіз көп плитканы саңылаусыз қатар орналастырып, шексіз үлкен жарық жолағы өрнегін құраймыз.

Қолжетімді $k$ әртүрлі түс бар, және сізге бір плиткадағы барлығы $2n^2$ жарық жолағына сәйкес түстерді таңдау керек, содан кейін басқа плиткалар бұл бояу сұлбасын автоматты түрде қайталайды. Плиткаларды төсеу кезінде барлық плиткалар бір бағытта төселеді, яғни оларды бір плитканы бұрмай тікелей параллель көшіріп, содан кейін біріктірілген деп қарастыруға болады.

Еден үстімен жүріп келе жатып, сіз плиткаларды бояудың мәні бойынша әртүрлі қанша сұлбасы бар екенін білгіңіз келеді. Еден шексіз болғандықтан және адам плиткаларды бақылаған кезде әртүрлі бағыттарға (солтүстік, оңтүстік, шығыс, батыс) қарап тұруы мүмкін болғандықтан, екі сұлба келесі жағдайда және тек сол жағдайда ғана мәні бойынша бірдей деп анықталады:

Екі сұлба арқылы жасалған шексіз еден жазықтығын бақылаған кезде, едендегі барлық орындардағы жарық жолақтарының түстерін толығымен бірдей ете алатын параллель көшірулер немесе бұрулар тізбегі (шағылыстыруды қоспағанда) табылса, онда бұл екі сұлба мәні бойынша бірдей деп есептеледі.

Кіріс деректер

Бір тест файлында бірнеше тест жиынтығы бар. Кірістің бірінші жолында тест жиынтықтарының санын білдіретін бір оң бүтін сан $T$ ($1 \le T \le 10$) берілген.

Әрбір тест жиынтығы үшін:

• Бірінші жолда өрнектің өлшемін және түстердің санын білдіретін екі бүтін сан $n$ мен $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$) берілген.

Шығыс деректер

Әрбір тест жиынтығы үшін бір жолға бір бүтін санды — мәні бойынша әртүрлі сұлбалар санын $10^9 + 7$ модулі бойынша шығарыңыз.

Мысал

Кіріс деректер 1

3
1 2
2 2
114514 5201314

Шығыс деректер 1

3
31
377726028

Ескертпе

Төмендегі суретте $n = k = 2$ болғандағы 19 құрастыру сұлбасы көрсетілген (плитка төсеу әсерін жақсырақ көрсету үшін әрбір суретте $3 \times 3$ үлгісінде орналасқан 9 плитка көрсетілген, LED шамдары күңгірт және ашық түстерде берілген). Алғашқы 12 сұлбаның күңгірт және ашық түстерін өзара ауыстыру арқылы тағы 12 сұлба алуға болады, нәтижесінде барлығы 31 сұлба шығады.