Hide
Problem D
Classical Counting
You have $N$ objects, each with $M$ copies. How many ways are there to take exactly $K$ of them?
Two selections of size $K$ are considered different if the $K$-tuples for those selections are different. So, for example if $N=M=K=3$ (as in the second sample input), and the $N=3$ types of objects are labeled $A$, $B$, and $C$, then the tuple $(A,B,B)$ is different than $(B,A,B)$.
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$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 1 2 |
45 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 3 |
10 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 2 7 |
0 |
