- 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.
The only input line has two integers: n and k.
Print one integer: the answer modulo 10^9+7.
- 1 \le k \le n \le 10^6
Explanation: The valid strings are 010, 011, 101, 110 and 111.