問題文

$\mathcal{G}1$ と $\mathcal{G}2$ はほとんど同じ問題だが, 制約と実行時間制限が異なる.

チェリーちゃんは今回のコンテストの開催を記念して, 以下を満たすようなオブジェを作ることになった.

• $\Gamma_N$ は以下を満たすような正 $N$ 角柱である.
• 底面は1辺の長さが $1$ の正 $N$ 角形である.
• 側面のうち, 2つの底面の頂点同士を結ぶ辺の長さはすべて $2$ である.
• 全ての側面は底面と直交している.
• $\Gamma_N$ にある $2N$ 個の頂点それぞれについて, 色 $1, \dots,$ 色 $C$ の計 $C$ 色の中から $1$ 色を選んで塗る.

ただし, 既にあるオブジェと似ているオブジェを作ってしまうと, SNS で炎上してしまう. また, 今はそうでなくても, 後々似たものが出てきても流れ弾を喰らって面倒くさいことになってしまう. このことを懸念したチェリーちゃんは上のような条件下でどのくらいオブジェクトを作ることができるかが気になった. そこで, $N, C$ が与えられるので, 以下の問題の答えを求めよ.

• $\Gamma_N$ にある $2N$ 個の頂点の彩色で, 回転によって一致する場合を区別しない場合の彩色の方法は何通りか? $10^9+7$ で割った余りを出力せよ.

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 10$
• $3 \leq N \leq 10^9$
• $1 \leq C \leq 10^9$
• 入力は整数である.

入力

入力は標準入力から与えられる. 入力の $1$ 行目は以下の形式である.

$T$

$N$ $C$

出力

出力は全部で $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースでの $\Gamma_N$ にある $2N$ 個の頂点の彩色で, 回転によって一致する場合を区別しない場合の彩色の方法の数を $10^9+7$ で割った余りを出力せよ.

ただし, 改行を忘れないこと.

サンプル

3
3 2
5 1
46 20211031

16
1
173884620