無限に広い床の上に、無限個のタイルを敷き詰める必要があります。

各タイルにはサイズ $n \times n$ の正方形のグリッド模様があります。タイルの各グリッドセルの下辺と左辺には LED ライトテープが固定されており、異なる色によってカラフルな模様を作り出しています。

各タイルの模様は完全に同じです。タイルを敷き詰める際、無限個のタイルを隙間なく並べて配置し、無限に広いライトテープの模様を形成します。

利用可能な色は $k$ 種類あり、1 枚のタイル上の合計 $2n^2$ 本のライトテープに対応する色を選ぶ必要があります。その後、他のタイルにはこの配色パターンが自動的に複製されます。タイルを敷き詰める際、すべてのタイルは同じ向きで敷かれます。つまり、1 枚のタイルを回転させずにそのまま平行移動して繋ぎ合わせたものとして見なすことができます。

床の上を歩きながら、タイルの配色として本質的に異なるものが何通りあるかを知りたいです。床は無限に広く、タイルを観察する人は異なる方角（東、南、西、北）を向く可能性があるため、2 つの配色は次の条件を満たすとき、かつそのときに限り本質的に同じであると定義されます：

2 つの配色によって作られる無限の床平面を観察したとき、一連の平行移動または回転（反転・鏡像は含まない）によって床上のすべての位置のライトテープの色を完全に一致させることができるならば、これら 2 つの配色は本質的に同じであると見なされます。

入力

1 つのテストファイルに複数のテストケースが含まれます。入力の 1 行目には、テストケースの数を表す正の整数 $T$ ($1 \le T \le 10$) が与えられます。

各テストケースについて：

• 入力の 1 行目には、模様のサイズと色の数をそれぞれ表す 2 つの整数 $n$ と $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$) が与えられます。

出力

各テストケースについて、本質的に異なる配色の数を $10^9 + 7$ で割った余りを表す整数を 1 行に出力してください。

サンプル

入力例 1

3
1 2
2 2
114514 5201314

出力例 1

3
31
377726028

注記

以下の画像は $n = k = 2$ のときの 19 通りの構成方法を示しています（タイルの敷き詰め効果をより分かりやすく示すため、各画像には $3 \times 3$ の形で並べられた 9 枚のタイルが描かれており、LED には濃色と淡色の 2 色が使われています）。最初の 12 通りの構成における濃色と淡色を入れ替えることでさらに 12 通りの構成が得られ、合計で 31 通りとなります。