M. 晚饭吃什么？
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"晚饭吃什么？" "我都行。"

notPP 罗列了 $$$m$$$ 个吃饭的地点，在接下来的 $$$n$$$ 天中，notPP 觉得一直吃外卖会腻，于是他决定拿恰好 $$$k$$$ 天出来去外面吃饭。

但连续两天都在同一个地方吃饭容易腻，于是他希望"不能连续两天都去同一个地方吃饭（外卖除外）"的规则。

在这种情况下，请问 notPP 有多少种方案呢？因为答案可能很大，所以请将其对 $$$10^9+7$$$ 取模。

Input

本题每个测试点有多组测试数据。

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 10^5$$$)，表示有 $$$T$$$ 组测试样例。

接下来对于每组样例：

一行输入三个数字 $$$n,m,k$$$ ($$$1 \leq k \leq n \leq 10^6$$$, $$$1 \leq m \leq 10^6$$$)，分别代表接下来 $$$n$$$ 天，有 $$$m$$$ 个吃饭的地方和分配 $$$k$$$ 天。

保证单个测试点的所有测试数据的 $$$n$$$ 之和不超过 $$$10 ^ 6$$$。

Output

输出一行，表示分配方案的数量对 $$$10^9+7$$$ 取模得到的结果。

Example
Input
2
3 2 3
3 2 2
Output
2
8
Note

对于第一个样例，notPP 在接下来的 $$$3$$$ 天都去外面吃，故有两种情况：$$$\{1,2,1\}$$$ 和 $$$\{2,1,2\}$$$。

对于第二个样例，这里有所有的可行情况（其中 $$$0$$$ 表示外卖）：

$$$\{1,2,0\},\{2,1,0\},\{1,0,1\},\{1,0,2\},\{2,0,1\},\{2,0,2\},\{0,1,2\},\{0,2,1\}$$$