Signal Frame Without k Consecutive Highs

MediumCombinatoricsCountingBinary-StringsDynamic-ProgrammingModular-Arithmetic5 hidden tests

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.

Input format

A single line with two integers n and k.

Output format

A single integer: the number of valid frames, modulo 1000000007.

Constraints

1 <= n <= 18
1 <= k <= 20

Examples

Example 1

Input

3 2

Expected

Explanation

No run of 2 or more 1s in 3 bits: 000,001,010,100,101 = 5.

Example 2

Input

2 3

Expected

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 →