A transmitter sends a frame of n bits, each bit LOW (0) or HIGH (1). To avoid overheating, the frame must never contain a run of k or more consecutive HIGH bits. Count how many distinct frames of length n satisfy this rule. Report the count modulo 1000000007.
A single line with two integers n and k.
A single integer: the number of valid frames, modulo 1000000007.
Example 1
Input
3 2
Expected
5
Explanation
No run of 2 or more 1s in 3 bits: 000,001,010,100,101 = 5.
Example 2
Input
2 3
Expected
4
Explanation
A run of 3 cannot fit in 2 bits, so all 2^2 = 4 frames are valid.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →