No K Ones in a Row

Difficulty: 2000 4000 ms 128 MB

dp matrix-exponentiation

Count the binary strings of length N with no K consecutive 1s, modulo 10⁹+7.

Input: one line with two integers N and K.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸
• 1 ≤ K ≤ 6

Sample Tests

3 2

5

1 1

1

Read the Editorial