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.