为了吸引顾客，店主决定订购一个特殊的霓虹灯招牌放置在店门前。这个特殊的霓虹灯招牌由几个梯形组件组成。每个梯形组件可以用梯形图 $L_n$ 表示，这是一个平面无向图，具有 $2n$ 个顶点和 $3n-2$ 条边。每个顶点代表霓虹灯的一个灯泡，每条边代表连接两个灯泡的导线。梯形图可以通过两个路径图的笛卡尔积获得，其中一个路径图仅有一条边：$L_n = P_n \times P_2$，其中 $P_n$ 是具有 $n$ 个顶点的路径图。图 1 展示了 $L_6$。用于固定 $k$ 个梯形组件的主框架是一个 $k$ 正多边形。$k$ 正多边形的每条边都与 $L_n$ 的顶边相结合。图 2 展示了 $k=3$ 且 $n=4$ 的情况，图 3 展示了 $k=4$ 且 $n=3$ 的情况。为了便于描述，霓虹灯招牌由灯泡（顶点）和导线（边）组成的图 $G = (V, E)$ 表示。为了使霓虹灯更加耀眼，设计师 Ray 想出了一种指定 $G$ 中灯泡（顶点）颜色的方法。Ray 希望为灯泡分配颜色，使得满足以下条件：如果 $G$ 的顶点分配颜色后，使得相邻的顶点颜色不同，则称该着色为 $G$ 的合法着色。$G = (V, E)$ 中的灯泡是可区分的，即灯泡由标签 $v_1, v_2, \dots, v_m$ 命名。因此，如果 $G$ 的灯泡的合法着色（使用最多 $\lambda$ 种颜色）是一个函数 $f$，其定义域为 $V$，陪域为 $\{1, 2, 3, \dots, \lambda\}$，且对于相邻顶点 $u, v \in V$ 满足 $f(u) \neq f(v)$，则认为两种灯泡颜色分配方式不同。合法着色方式的不同，等同于这些函数本身的不同。使用 $\lambda$ 种颜色对 $G$ 进行着色的不同方式的最大数量称为 $G$ 的色数（critical number）。

图 1: $L_6$。

图 2: $k=3$ 且 $n=4$ 的示例。

图 3: $k=4$ 且 $n=3$ 的示例。

给定 (1) $n$（用于 $L_n$），(2) $k$（用于 $k$ 正多边形），以及 (3) 可用颜色数量 $\lambda$，你的任务是计算 $G$ 的色数。注意，如果结果大于或等于 $10^9 + 7$，你应该输出该值对 $10^9 + 7$ 取模的结果，即实际值除以 $10^9 + 7$ 得到的余数。

输入格式

输入文件的第一行包含一个整数 $L$ ($L \le 20$)，表示测试用例的数量。对于每个测试用例，第一行包含三个整数（以空格分隔），分别表示 $n, k$ 和 $\lambda$。

数据范围

• $1 \le n \le 1000000000$。
• 每个测试用例 $3 \le k \le 1000000000$。
• $0 \le \lambda \le 1000000000$。

输出格式

输出包含每个测试用例的一行。每行包含一个非负整数，表示 $G$ 的色数。注意，如果结果大于或等于 $10^9 + 7$，你应该输出该值对 $10^9 + 7$ 取模的结果，即实际值除以 $10^9 + 7$ 得到的余数。

样例

输入 1

1
2 3 3

输出 1

162