We have n empty boxes, so let’s recolor those boxes with m colors.
The boxes are put in a line. It is not allowed to color any adjacent boxes with the same color. Boxes i and i+1 are said to be adjacent for every i,1≤i≤n.
And we also want the total number of different colors of the n boxes being exactly k.
Two ways are considered different if and only if there is at least one box being colored with different colors.
输入描述:
The first line of the input contains integer T(1≤T≤100) -the number of the test cases
For each case: there will be one line, which contains three integers n,m,k(1≤n,m≤109 1≤k≤106, k≤n,m).
输出描述:
For each test case, you need print an integer means the number of ways of different coloring methods modulo 109+7.
示例1
说明
In the first example we have two ways:
121
212
where 1 and 2 are two different color.
In the second example we can't do that.