Gift
Karev really enjoys simple sequences of at most K numbers. A simple sequence oflength K is a sequence formed by the numbers from 0 to K-1 in this order. For example,simple sequences are {0}, {0,1,2,3}, {0,1,2,3,4,5,6}, while the sequences {1}, {0,1,3,2}, {0,1,3} – are not.
Since Karev’s birthday is approaching, Polly would like to buy for him a few simplesequences and combine them into an interesting sequence. An interesting sequence is asequence formed by concatenating a few simple sequences, each with length at most K. Forexample, let K = 3. Then {0,1,2,0}, {0,1,0,1}, {0,0,0} and {0,1,2} are interesting sequences, but {0,1,2,3}, {0,1,1} and {0,0,2} are not.
Since Polly can choose many sequences, she is wondering which one to pick. Now she is curious how many choices she really has. Karev is a very good friend of Polly so she might decide to buy a really huge present for him.
Write a program to help Polly by solving the following problem: Given K – the maximum length of the simple sequences that Polly can buy, and N – the length of the interesting sequence that she wants to form, calculate how many different interesting sequences she could make. Since this number can be very large, output it modulo 10^9+7.
####InputTwo numbers separated by space are given on the first line of the standard input – N and K(1 ≤ K ≤ N ≤ 2000000 ), respectively.
####OutputYou should output a single number on the first line of the standard output – thenumber of different interesting sequences Polly can make with the current constraints.Output the answer modulo 10^9+7.
####Explanation for the first sample caseLet K=3 and N=4. The possible interesting sequencesare {0,0,0,0}; {0,0,0,1}; {0,0,1,0}; {0,0,1,2}; {0,1,0,0}; {0,1,0,1}; {0,1,2,0}. Hence there are 7 sequences and this is the answer for this example.