Auf einem unendlich großen Boden musst du unendlich viele Fliesen verlegen.

Jede Fliese hat ein quadratisches Gittermuster der Größe $n \times n$. Jede Gitterzelle der Fliese hat entlang ihrer unteren und linken Kante einen fest angebrachten LED-Leuchtstreifen in verschiedenen Farben, wodurch ein buntes Muster entsteht.

Das Muster auf jeder Fliese ist exakt dasselbe. Beim Verlegen der Fliesen platzieren wir unendlich viele Fliesen nahtlos nebeneinander, sodass ein unendlich großes Leuchtstreifenmuster entsteht.

Es stehen $k$ verschiedene Farben zur Verfügung, und du musst für insgesamt $2n^2$ Leuchtstreifen auf einer Fliese die entsprechenden Farben auswählen, woraufhin die anderen Fliesen dieses Farbschema automatisch übernehmen. Beim Verlegen werden alle Fliesen in derselben Ausrichtung verlegt, was bedeutet, dass sie als direkte Verschiebung einer einzelnen Fliese ohne Drehung betrachtet werden können, die anschließend zusammengefügt werden.

Während du über den Boden gehst, möchtest du wissen, wie viele wesentlich verschiedene Farbschemata es für die Fliesen gibt. Da der Boden unendlich groß ist und eine Person beim Betrachten der Fliesen in verschiedene Himmelsrichtungen (Norden, Süden, Osten, Westen) blicken kann, gelten zwei Schemata genau dann als wesentlich gleich, wenn Folgendes gilt:

Wenn beim Betrachten der durch die beiden Schemata erzeugten unendlichen Bodenebene eine Folge von Verschiebungen oder Drehungen (Spiegelungen ausgeschlossen) existiert, durch die die Farben der Leuchtstreifen an allen Positionen auf dem Boden vollständig übereinstimmen, dann gelten diese beiden Schemata als wesentlich gleich.

Eingabe

Es gibt mehrere Testfälle in einer einzigen Eingabedatei. Die erste Zeile der Eingabe enthält eine einzelne positive ganze Zahl $T$ ($1 \le T \le 10$), die die Anzahl der Testfälle angibt.

Für jeden Testfall gilt:

• Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$), die die Größe des Musters bzw. die Anzahl der Farben darstellen.

Ausgabe

Gib für jeden Testfall eine einzige Zeile mit einer ganzen Zahl aus, die die Anzahl der wesentlich verschiedenen Schemata modulo $10^9 + 7$ angibt.

Beispiel

Eingabe 1

3
1 2
2 2
114514 5201314

Ausgabe 1

3
31
377726028

Hinweis

Das folgende Bild zeigt 19 Konstruktionsschemata für $n = k = 2$ (um den Flieseneffekt besser zu veranschaulichen, zeigt jedes Bild 9 Fliesen, die in einem $3 \times 3$-Muster angeordnet sind, wobei die LEDs in einer dunklen und einer hellen Farbe dargestellt sind). Durch Vertauschen der dunklen und hellen Farbe der ersten 12 Schemata erhält man weitere 12 Schemata, was insgesamt 31 Schemata ergibt.