You need to install night lighting along the road. Working team has already installed n lanterns, it remains only to turn them on. To save money, it was decided to turn on such number of lanterns so that it will be safe to ride on this road. Road is considered safe if any its section does not contain k neighboring switched off lanterns.

Your task is to figure out in how many ways you can turn on illumination on the road so as to go through it is safely. Two variants of illumination are considered different if there is at least one lantern that is turned on in the first version, and is turned off in the second, or vice versa. Because the answer may be very large, output the answer modulo 109 + 7.

Input

Two integers n (1 ≤ n ≤ 106) and k (1 ≤ k ≤ n).

Output

Print the number of ways to turn on the road's illumination so that it becomes safe.