The grasshopper jumps on columns located on the same line at equal distances from each other. The columns have serial numbers from 1 to N . At the beginning, the Grasshopper sits on a post with the number 1. It can jump forward from 1 to K bars, counting from the current one. It is required to find the number of ways in which the Grasshopper can get to the column with the number N. Keep in mind that the Grasshopper cannot jump backwards.
Since the number of ways to find can be very large, modulo \(10^6 + 7\) , i.e. find the remainder of the division this number to \(10^6 + 7\) .
Input: The input string contains natural numbers N and K separated by a space. It is guaranteed that \(1 <= N ,\ K <= 10000\).
Output: The program should print a single number: the number of ways the Grasshopper can get to the column numbered N calculated from module \(10^6+7\).
Examples
| # |
Input |
Output |
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |