I. The Binary Escape Challenge
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this challenge, you are tasked with helping the players navigate through a series of binary gates. The guards have set up a system where each gate is either "open" (denoted by $$$1$$$) or "closed" (denoted by $$$0$$$). The challenge is to escape through the gates by ensuring you have a segment of open gates large enough to slip through without being caught.

You are given two integers,$$$n$$$ — the total number of gates (binary sequence length)and $$$l$$$ — the minimum number of consecutive open gates (i.e., $$$1s$$$) required to successfully escape.

Your task is to determine how many binary sequences of length $$$n$$$ contain at least one contiguous subsegment of length $$$l$$$ consisting only of $$$1s$$$. The sequence can contain any combination of $$$0s$$$ and $$$1s$$$, but to successfully escape, there must be a subsegment of $$$l$$$ consecutive $$$1s$$$ somewhere in the sequence.

Since the number of such sequences can be quite large, output the result modulo $$$10^9+7$$$.

Input

A single line containing two integers $$$n$$$ $$$(1 \leq n \leq 10^9)$$$ and $$$l$$$ $$$(1 \leq l \leq 100)$$$ respectively representing the total number of gates and the minimum number of consecutive open gates required to successfully escape.

Output

Output a single integer — the number of valid binary sequences of length $$$n$$$ that satisfy the condition, modulo $$$10^9+7$$$.

Example
Input
3 2
Output
3
Note

In the first test, all possible sequences of gates are :

$$$000,001,010,011,100,101,110,111$$$.

The only valid ones are :

$$$011,110,111$$$.

So the answer is 3.