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.