Gift

Karev really likes simple sequences of length at most $K$. A simple sequence of length $L$ is the sequence of the numbers from $0$ to $L-1$ written in this order. For example, $\{0\}$, $\{0,1,2,3\}$ and $\{0,1,2,3,4,5,6\}$ are simple sequences, while $\{1\}$, $\{0,1,3,2\}$ and $\{0,1,3\}$ are not.

Karev's birthday is close, so Polly wants to buy a few simple sequences and concatenate them into an interesting sequence. An interesting sequence is a sequence obtained by concatenating several simple sequences, each of length at most $K$. For example, let $K=3$. Then $\{0,1,2,0\}$, $\{0,1,0,1\}$, $\{0,0,0\}$ and $\{0,1,2\}$ are interesting sequences, while $\{0,1,2,3\}$, $\{0,1,1\}$ and $\{0,0,2\}$ are not.

Polly has so many sequences to choose from that she cannot decide which one to pick, and she wonders how many choices she really has.

Given $K$, the maximum length of a simple sequence Polly can buy, and $N$, the length of the interesting sequence she wants to form, write a program that counts the different interesting sequences she could make. This number can be very large, so output it modulo $10^9+7$.

The first line contains two integers $N$ and $K$, in this order, separated by a space.

Print on the first line the number of different interesting sequences Polly can make, modulo $10^9+7$.

• $1 \le K \le N \le 2 \times 10^6$

For $N=4$ and $K=3$ the possible interesting sequences are $\{0,0,0,0\}$, $\{0,0,0,1\}$, $\{0,0,1,0\}$, $\{0,0,1,2\}$, $\{0,1,0,0\}$, $\{0,1,0,1\}$ and $\{0,1,2,0\}$, so the answer is 7.