Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

E. Erudite of words
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ivanovich is highly considered an Erudite of words.

But Ivanovich doesn't know what it means, maybe is about knowing a lot of words, and the ability to use them in the right context is not important.

So Crystalovich wanted to test how good of an Erudite is Ivanovich, so she asked him how many words there are with length $$$N$$$ using an alphabet of $$$M$$$ different letters.

Francovich hearing the problem thought it was very easy, and he doesn't like easy problems, so he added a condition such that each word have to use exactly $$$K$$$ different letters.

Help Ivanovich answer the question, since the answer can be very large print it module $$$10^9 + 7$$$

Input

The first and only one line contains three integers $$$N$$$, $$$M$$$ and $$$K$$$ with ($$$1 \leq N \leq 10^6$$$) ($$$1 \leq K \leq M \leq 5 \times 10^3$$$) representing the length of the word, the size of the alphabet, and the number of different letters that the words should have.

Output

A single number indicating the numbers of words modulo $$$10^9 + 7$$$

Examples
Input
3 3 3
Output
6
Input
5 2 2
Output
30
Input
1000 1000 1
Output
1000