Na nieskończenie dużej podłodze musisz ułożyć nieskończenie wiele płytek.

Każda płytka ma wzór kwadratowej siatki o wymiarach $n \times n$. Każda komórka siatki na płytce ma pasek świetlny LED przymocowany wzdłuż jej dolnej oraz lewej krawędzi; paski te mają różne kolory, tworząc barwny wzór.

Wzór na każdej płytce jest dokładnie taki sam. Podczas układania płytek umieszczamy nieskończenie wiele płytek bezszwowo obok siebie, tworząc nieskończenie duży wzór z pasków świetlnych.

Dostępnych jest $k$ różnych kolorów i musisz wybrać odpowiednie kolory dla łącznie $2n^2$ pasków świetlnych na jednej płytce, po czym pozostałe płytki automatycznie powielą ten schemat kolorowania. Podczas układania wszystkie płytki będą kładzione w tym samym kierunku, co oznacza, że można je traktować jako bezpośrednie przesunięcie (translację) pojedynczej płytki i sklejenie ich ze sobą bez obracania.

Spacerując po podłodze, chcesz wiedzieć, ile jest istotnie różnych schematów kolorowania płytek. Ponieważ podłoga jest nieskończona, a osoba obserwująca płytki może być zwrócona w różnych kierunkach (północ, południe, wschód, zachód), dwa schematy definiujemy jako istotnie takie same wtedy i tylko wtedy, gdy:

Podczas obserwacji nieskończonej płaszczyzny podłogi utworzonej przez te dwa schematy istnieje ciąg przesunięć lub obrotów (z wyłączeniem odbić lustrzanych), który sprawia, że kolory pasków świetlnych we wszystkich miejscach na podłodze stają się całkowicie identyczne — wówczas te dwa schematy uznaje się za istotnie takie same.

Wejście

W jednym pliku testowym znajduje się wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną dodatnią liczbę całkowitą $T$ ($1 \le T \le 10$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), oznaczające odpowiednio rozmiar wzoru oraz liczbę kolorów.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu jedną liczbę całkowitą, oznaczającą liczbę istotnie różnych schematów modulo $10^9 + 7$.

Przykład

Wejście 1

3
1 2
2 2
114514 5201314

Wyjście 1

3
31
377726028

Uwaga

Poniższy obrazek przedstawia 19 schematów konstrukcyjnych dla $n = k = 2$ (aby lepiej zilustrować efekt ułożenia płytek, każdy obrazek pokazuje 9 płytek ułożonych we wzór $3 \times 3$, z diodami LED w kolorze ciemnym i jasnym). Zamieniając miejscami kolory ciemny i jasny w pierwszych 12 schematach, można uzyskać kolejne 12 schematów, co daje łącznie 31 schematów.