P5004 Focus on OI - Hopscotch

Imakf once participated in the PINO2017 PJ division, and suddenly saw the last problem:  He was very weak and could not solve it. Now he is still weak, and he saw another problem:  He still could not solve it, so he came to ask you for help.

You have $N$ cells arranged in a line, numbered from left to right as $1,2,\cdots,N$. You stand infinitely far to the left of cell $1$, and start jumping from left to right, until you reach the right side of cell $N$. Since you are a successful OIer, you are naturally very heavy, so your legs are very strong. This means that for each jump, there must be at least $M$ empty cells between the current cell and the target cell, but you can jump arbitrarily far. You think jumping like this is too boring, so you want to calculate how many different ways there are to complete the whole journey. Since the number of ways may be too large, output the number of ways modulo $(10^9+7)$. Two ways are different if and only if there exists at least one visited cell whose index is different.

The first line contains two integers $N,M$.

Output one integer, the number of ways to complete the whole journey modulo $(10^9+7)$.

| Testdata ID | $N$ | $M$ | | :-----------: | :-----------: | :-----------: | | $1,2$ | $\leq10$ | $=1$ | | $3,4$ | $\leq10^7$ | $=1$ | | $5,6$ | $\leq10^6$ | $=2$ | | $7,8$ | $\leq10^5$ | $=3$ | | $9,10$ | $\leq10^4$ | $=5$ | | $11,12$ | $\leq10^{12}$ | $=1$ | | $13,14$ | $\leq10^{18}$ | $=10$ | | $15\sim20$ | $\leq10^{18}$ | $=15$ | For $100\%$ of the data, $1 \le N \le 10^{18}$. Translated by ChatGPT 5