Number of NKD Sequences

Time limit2sMemory limit512 MB

Summary

Count length-K strictly increasing sequences summing to N where consecutive differences are at most D and the first term is at most D, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Sliding window
Solved: No attempts yet

Problem

You are given three integers $N$ , $K$ , and $D$ . Count the natural-number sequences $A_1, A_2, \dots, A_K$ of length $K$ that satisfy all of the following conditions.

$A_1 + A_2 + \dots + A_K = N$
$A_1 < A_2 < \dots < A_K$
For every $1 \le i < K$ , $A_{i+1} - A_i \le D$
$A_1 \le D$

Input

The first line contains three integers $N$ , $K$ , and $D$ , separated by spaces.

Output

Print the number of sequences satisfying the conditions, modulo $10^9 + 7$ .

Constraints

$1 \le N, K, D \le 10^5$

Examples1

Example 1
Input
```
10 4 1
```
Expected output
```
1
```