E. Enumerating Substrings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There's an alphabet of size $$$k$$$. For a string $$$S$$$ in this alphabet (the text), and string $$$P$$$ (the pattern), let $$$F(S,P) = $$$ the maximum number of non-overlapping substrings you can take in $$$S$$$, that are equal to $$$P$$$.

Let's call a string $$$Q$$$ beautiful, if each letter in it occurs no more than $$$2$$$ times.

Over all possible strings of size $$$n$$$, and all possible beautiful patterns $$$P$$$ of size $$$m$$$, calculate the sum of $$$F(S,P)$$$. Because this sum can be huge, output the result modulo $$$10^9 + 7$$$.

Input

The first and only line of the input contains $$$3$$$ integers, $$$n,m,k$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq m \leq 2000$$$, $$$m \leq n$$$ and $$$1 \leq k \leq 10^9$$$)  — respectively, the length of string $$$S$$$, the length of the pattern $$$P$$$ and the alphabet size.

Output

Print a single line, containing one integer  — the sum of $$$F(S,P)$$$ over all strings $$$S$$$ and beautiful strings $$$P$$$ modulo $$$10^9 + 7$$$.

Examples
Input
4 2 3
Output
228
Input
999999 1999 12345678
Output
52352722