Problem Description

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$.

3
1 1 1
2 3 3
3 5 8

1
6
168

Hint

For the second sample, "ab,ac,ba,bc,ca,cb" is satisfied.