A. Whopper Junior
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Boy Yaroslav wanted to eat $$$n$$$ whoppers for lunch. First he eats the first whopper, then the second, the third, and so on. The tastiness of the $$$i$$$-th whopper is $$$a_i$$$.

Since Yaroslav has ADHD, it is hard for him to eat a whopper when its tastiness is different from the tastiness of the previous whopper he ate, so he can do this exactly $$$m$$$ times. He became interested in how many different sequences of whoppers he can eat if the tastiness of each whopper can be any integer from $$$1$$$ to $$$k$$$.

More formally, you need to count the number of sequences $$$a$$$ of length $$$n$$$, consisting of numbers from $$$1$$$ to $$$k$$$, such that there are exactly $$$m$$$ indices $$$i$$$ ($$$2 \le i \le n$$$) for which $$$a_i \ne a_{i-1}$$$.

Since the number of such sequences can be very large, print the answer modulo $$$10^9 + 7$$$.

Input

The only line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$0 \le m \lt n \le 10^7$$$, $$$1 \le k \le 10^9$$$) — the number of whoppers, the number of transitions between whoppers with different tastiness, and the maximum possible tastiness of a whopper.

Output

Print one integer — the number of whopper sequences that Yaroslav can eat, modulo $$$10^9 + 7$$$.

Scoring

The tests for this problem consist of four groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.

SubtaskPointsAdditional constraintsRequired subtasks
$$$n$$$additionally
$$$1$$$$$$20$$$$$$n \le 8$$$$$$k \le 8$$$S
$$$2$$$$$$15$$$—$$$m = n - 1$$$—
$$$3$$$$$$25$$$$$$n \le 1\,000$$$—S, 1
$$$4$$$$$$40$$$——S, 1–3
Examples
Input
3 2 4
Output
36
Input
4 2 4
Output
108
Input
8 4 5
Output
44800