最近，Mr. Big 收到了粉丝送的 $n$ 朵花。他想用 $m$ 种颜色重新给这些花上色。这些花排成一行。不允许给相邻的两朵花涂上相同的颜色。对于每一朵花 $i$ 和 $i+1$（$1 \le i < n$），它们被认为是相邻的。Mr. Big 还要求这 $n$ 朵花所使用的不同颜色总数恰好为 $k$。

如果至少有一朵花的颜色不同，则认为两种涂色方案不同。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。$T$ 大约为 $300$，且在大多数情况下 $k$ 相对较小。

对于每个测试用例，输入一行，包含三个整数 $n, m, k$（$1 \le n, m \le 10^9, 1 \le k \le 10^6, k \le n, m$）。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是满足条件的涂色方案数对 $10^9 + 7$ 取模的结果。

样例

输入 1

2
3 2 2
3 2 1

输出 1

Case #1: 2
Case #2: 0