A radio beacon transmits messages of n bits. Sending a 1 heats the transmitter and sending a 0 lets it cool, and the hardware overheats if it ever sends k ones in a row. Return how many bit strings of length n are safe to send (contain no run of k consecutive 1s), modulo 10**9 + 7. For n = 0 the only message is the empty one.
Examples
Input: n = 3, k = 2
Output: 5
Explanation: 000, 001, 010, 100, 101.
Input: n = 4, k = 3
Output: 13
Explanation: all 16 strings except 1110, 0111 and 1111.
Constraints
0 <= n <= 10**5,1 <= k <= 10**5- Target complexity: O(n) time; an O(n * k) recurrence is too slow when both are large.
Goals
- Count strings by the length of the trailing block before the last 0
- Maintain a sliding window sum so each step is O(1) even for large k