409723: GYM103708 E Erudite of words

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

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.

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

3 3 3

6

5 2 2

30

1000 1000 1

1000