喺一個無限大嘅地板上面，你需要鋪設無限咁多塊階磚。

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