There are $n$ stones in a row from left to right. You are standing on the first stone. From every step from stone number $i$, you can jump at most $k$ stones further ($i + 1,\ i + 2,\ \dots,\ i + k$). You cannot jump over stone number $n$. How many ways are there to travel to stone number $n$?

Input format

First line: $n$ and $k$

Output format

Print the answer modulo $10^9+7$.