CSES - HIIT Open 2019 - 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.