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$.
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.$
For every test case output the answer modulo $10^9 + 7$.