Karev really enjoys simple sequences of at most K numbers. A simple sequence of length 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 simple sequences and combine them into an interesting sequence. An interesting sequence is a sequence formed by concatenating a few simple sequences, each with 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, 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 109+7.

Input

Two numbers separated by space are given on the first line of the standard input – N and K (1 ≤ K ≤ N ≤ 2000000 ), respectively.

Output

You should output a single number on the first line of the standard output – the number of different interesting sequences Polly can make with the current constraints. Output the answer modulo 109+7.

Explanation for the first sample case

Let K=3 and N=4. 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}; {0,1,2,0}. Hence there are 7 sequences and this is the answer for this example.