Candles And Kids :
Difficulty Level : Medium
Submissions : 65
Asked In :
Marks :10
: 6 | : 0
Given N identical candles, find the number of ways to distribute them among K kids so that there is no kid with more than M candles.
Output the answer modulo 1e9+7.
Input
Input consists of 3 space separated integers, N (1 <= N <= 1e5) , K (1 <= K <= 1e5) and M (1 <= M <= 1e5).
Output
Output a single integers, the number of ways to distribute modulo 1e9+7.
Examples
Input
3 2 2
Output
2
Input
1000 1000 1000
Output
36237869
Note
There can be 2 ways for distributing, (1 , 2) and (2 , 1).
