A Sum Of Coins :
Difficulty Level : Easy
Submissions : 2391
Asked In :
Marks :10
: 27 | : 1
You have N coins whose amount ranges from 0 to N-1 respectively. Your friend wants to take K coins out of your coins. You can only give the coins if the set of K coins is useful. A set of coins is useful if the sum of the coins is divisible by a given integer M.
Task: Determine the number of ways you can give your friend K coins. Since the answer can be large, print the answer modulo 10^9+7.
Constraints:
$$$1 \le N \le 10^3$$$
$$$1 \le M \le 10^3$$$
$$$1 \le K \le 10^2$$$
Input
The input line contains 3 space-separated integers N, K, and M.
Output
Print the answer modulo $$$10^9$$$+7.
Examples
Input
4 2 2
Output
2
Input
3 1 1
Output
3
Note
Example:
K = 1, N = 3, M = 1
You can take 0,1,2 coins. All are divisible by M = 1. So, the answer is 3.
