题目描述
Problem Background
One day, Imakf participated in the PINO2017 Junior Group and suddenly saw the last problem:
Being a novice, he couldn't solve it.
Now, still a novice, he encountered another problem:
He still couldn't solve it and decided to seek your help.
Problem Description
You have \( N \) squares arranged in a row, numbered from left to right as \( 1, 2, \cdots, N \). You start infinitely far to the left of the 1st square and jump to the right until you reach beyond the \( N \)-th square. As a successful OIer, you are naturally quite heavy, which means your leg strength is also very strong! This allows you to jump such that there must be at least \( M \) empty squares between your current square and your target square, but you can jump an unlimited distance!
You find this jumping method uninteresting and want to calculate how many different ways you can complete the journey. Since the number of ways might be too large, you will output the number of ways modulo \( (10^9 + 7) \).
Two ways are considered different if and only if they pass through any different square numbers.
Input Format
The first line contains two integers \( N \) and \( M \).
Output Format
An integer representing the number of ways to complete the journey modulo \( (10^9 + 7) \).
Sample Input and Output
Sample Input #1
5 1
Sample Output #1
13
Sample Input #2
6 2
Sample Output #2
13
Notes
| Test Case Number | \( N \) | \( M \) |
|---|---|---|
| 1, 2 | \(\leq 10\) | \(= 1\) |
| 3, 4 | \(\leq 10^7\) | \(= 1\) |
| 5, 6 | \(\leq 10^6\) | \(= 2\) |
| 7, 8 | \(\leq 10^5\) | \(= 3\) |
| 9, 10 | \(\leq 10^4\) | \(= 5\) |
| 11, 12 | \(\leq 10^{12}\) | \(= 1\) |
| 13, 14 | \(\leq 10^{18}\) | \(= 10\) |
| 15 to 20 | \(\leq 10^{18}\) | \(= 15\) |
For \( 100\% \) of the data, \( 1 \le N \le 10^{18} \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分