题目描述

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

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

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

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

输入格式

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

第一行输入一个正整数 $T$ ，表示有 $T$ 组测试样例。

接下来对于每组样例：

一行输入三个数字 $n,m,k$ ，分别代表接下来 $n$ 天，有 $m$ 个吃饭的地方和分配 $k$ 天。

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

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

2
3 2 3
3 2 2

2
8

对于第一个样例， $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$ }

$1≤T≤10^5$ ， $1≤k≤n≤10^6$ ， $1≤m≤10^6$