店の客を引きつけるため、店主は店先に置く特別なネオンサインを注文することにした。このネオンサインは、いくつかのはしご型の部品からなる。各部品は、頂点が $2n$ 個、辺が $3n-2$ 本の平面的な無向グラフであるはしごグラフ $L_n$ で表せる。各頂点は電球、各辺は 2 つの電球をつなぐ電線を表す。はしごグラフは 2 つのパスグラフの直積として得られ、その一方は辺が 1 本だけである。すなわち $L_n=P_n\times P_2$ で、$P_n$ は $n$ 頂点のパスである。図 1 は $L_6$ を示す。$k$ 個のはしご型部品を支える主な枠は正 $k$ 角形である。

図 1：$L_6$。

正 $k$ 角形の各辺を $L_n$ の上端の辺と組み合わせる。図 2 は $k=3$、$n=4$ の場合を、図 3 は $k=4$、$n=3$ の場合を示す。説明のため、ネオンサインを電球（頂点）と電線（辺）からなるグラフ $G=(V,E)$ で表す。ネオンの光をよりきらびやかにするため、

図 2：$k=3$、$n=4$ の例。

デザイナーの Ray は、$G$ の電球（頂点）の色を指定する方法を考えた。Ray は次の条件が満たされるように電球に色を割り当てたい。$G$ の頂点に色を割り当て、$u$ と $v$ が隣接するときに異なる色になっていれば、その彩色を適正と呼ぶ。$G=(V,E)$ の電球は区別され、$v_1,v_2,\ldots,v_m$ というラベルで名付けられている。したがって、最大 $\lambda$ 色を使う $G$ の適正彩色は、定義域が $V$、終域が $\{1,2,3,\ldots,\lambda\}$ で、隣接頂点 $u,v\in V$ に対して $f(u)\ne f(v)$ を満たす関数 $f$ である。適正彩色が異なるとは、この関数が異なるということである。$\lambda$ 色を使って $G$ を彩色する異なる方法の最大数を、$G$ の臨界数と呼ぶ。

(1) $L_n$ に対する $n$、(2) 正 $k$ 角形に対する $k$、(3) 使用できる色数 $\lambda$ が与えられる。$G$ の臨界数を計算することがあなたの任務である。結果が $10^9+7$ 以上の場合は、$10^9+7$ で割った余り、すなわち実際の値を $10^9+7$ で割って得られる余りを出力せよ。

図 3：$k=4$、$n=3$ の例。

入力

入力ファイルの最初の行には、テストケース数を表す整数 $L$（$L\le20$）が与えられる。各テストケースの最初の行には、$n$、$k$、$\lambda$ を表す 3 つの整数が空白区切りで与えられる。

制約

• $1\le n\le1000000000$。

• 各テストケースについて $3\le k\le1000000000$。

• $0\le\lambda\le1000000000$。

出力

各テストケースについて 1 行出力せよ。各行には、$G$ の臨界数を表す非負整数を 1 つ出力せよ。結果が $10^9+7$ 以上の場合は、$10^9+7$ で割った余り、すなわち実際の値を $10^9+7$ で割って得られる余りを出力せよ。

入出力例

入力 1

1
2 3 3

出力 1

162