Stairway to the Moon

Limits: 2 sec., 256 MiB

It was the very special day. An extremely rare lunar eclipse, called super blue blood moon, was coming. Marichka told Zenyk that it will be very romantic to enjoy this phenomenon together. They decided to climb the roof of the highest building in Lviv to get a better view.

Unfortunately, the elevator was out of service and the couple had to go by stairs. On their way to the top, Marichka was thinking about selfies with the supermoon, and Zenyk came up with a new problem.

Suppose Zenyk needs to rise \(N\) stairs up. In one step he can rise up for an arbitrary number of stairs between \(1\) and \(N\). Let’s denote the number of stairs, Zenyk rises up in onle step, as the length of step. Zenyk has one rule: the difference between the longest and the shotest step should not exeed \(K\). The problem is to find the number of ways to rise \(N\) stairs up without violating the rule.

As long as the number of ways can be very large, you should print it out modulo \(10^9+7\) (i.e. you should print out the reminder of division of the number of ways by \(10^9+7\)).

Input

The only line of input contains two integer numbers, separated by space: \(N\) — the number of stairs and \(K\) — the largest allowed differenece between step lengths.

Output

A single number — the number of ways to rise \(N\) stairs up without violating Zenyk’s rule modulo \((10^9 + 7)\).

Constraints

\(1 \leq N,K \leq 100\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1	6

Notes

Let us consider the sample test case.

Here we have only 8 different ways to rise upstairs: \([1, 1, 1, 1]\), \([1, 1, 2]\), \([1, 2, 1]\), \([1, 3]\), \([2, 1, 1]\), \([2, 2]\), \([3, 1]\), \([4]\). Among them \([1, 3]\) and \([3, 1]\) violate the rule, because the difference between the longest and the shortest steps here is equal to \(3-1 = 2\) which is greater then \(1\).

Thus the answer here is 6.