How many string which the length is $n$, has $m$ different nonempty substring, and the character set size is $K$?
Since the answer will be very large, output the answer modulo $10^9+7$.
Input
The first line of the input is a integer $T$, meaning that there are $T$ test cases.
Then $T$ lines follow, each contain three integers $n, m, K$ as mentioned above.
$1 \leq T \leq 50,000.$
$1 \leq n \leq 10 ,1 \leq m \leq 100 ,1 \leq K \leq 1,000,000,000.$
Output
For every test case output the answer modulo $10^9 + 7$.
Sample Input
3
1 1 1
2 3 3
3 5 8
Sample Output
1
6
168
Hint
For the second sample, "ab,ac,ba,bc,ca,cb" is satisfied.
