在一個無限大的地板上，你需要鋪設無限多的瓷磚。

每塊瓷磚都有一個大小為 $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 種方案。