Units

Consider all possible strings of length n composed of zeros and ones. There are 2^n such strings in total. We are interested in counting the number of these strings that contain at least one segment of k consecutive ones. Due to the potentially large size of this number, you should output the remainder when this count is divided by 1000007.

Input

The input consists of two natural numbers, n and k, where 1 ≤ n ≤ 100000 and 1 ≤ k ≤ 100.

Output

Output the remainder when the number of strings containing at least one segment of k consecutive ones is divided by 1000007.

Examples