Chef Dengklek will open a new restaurant in the city. The restaurant will be open for N days. He can cook M different types of dish. He would like to cook a single dish every day, such that for the entire N days, he only cook at most K distinct types of dishes.

In how many ways can he do that?

------ Input ------

The first line contains a single integer T, the number of test cases. T test cases follow. Each test case consists of a single line consisting of three integers N, M, K.

------ Output ------

For each test case, output a single line consisting the number of different ways he can cook for the entire N days, modulo 1000000007.

------ Constraints ------

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
$1 ≤ M ≤ 1000000$
$1 ≤ K ≤ 1000$

----- Sample Input 1 ------
4
1 1 1
2 2 2
4 3 2
5 7 3
----- Sample Output 1 ------
1
4
45
5887

见题面

见题面