A vending machine is refilled by placing n identical bottles into k distinct slots. Every slot can hold from zero up to c bottles (its capacity). Count the number of ways to distribute all n bottles so that no slot exceeds its capacity c. Two distributions differ if some slot ends up with a different count. Report the count modulo 1000000007.
Input format
A single line with three integers n, k, and c.
Output format
A single integer: the number of valid distributions, modulo 1000000007.
Constraints
- 0 <= n <= 1000
- 1 <= k <= 1000
- 1 <= c <= 1000