Week 4 Homework [C1]

Start

2020-02-08 19:00 AKST

Week 4 Homework [C1]

End

2020-02-15 01:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -259 days 16:29:17

Time elapsed

150:00:00

Time remaining

0:00:00

Problem H
Classical Counting

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

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