You have $N$ objects, each with $M$ copies. How many ways are there to take exactly $K$ of them?

-----Input-----
The first line of input contains three integers, $N$, $M$ and $K$ respectively, subjected to $1 \leq N, M, K \leq 10^5$.

-----Output-----
Output the number of ways. As the number of ways could be large, output them modulo $10^6 + 7$.

-----Examples-----
Sample Input 1:
10 1 2
Sample Output 1:
45

Sample Input 2:
3 3 3
Sample Output 2:
10

Source: kattis | Difficulty: HARD


Solutions: