Bit Strings

• Time limit: 1.00 s
• Memory limit: 512 MB

Your task is to calculate the number of bit strings of length $n$ where each substring of length $k$ contains at least one 1.

Input

The only input line has two integers: $n$ and $k$.

Output

Print one integer: the answer modulo $10^9+7$.

Constraints

• $1 \le k \le n \le 10^6$
  

Example

Input:
3 2

Output:
5

Explanation: The valid strings are 010, 011, 101, 110 and 111.