Strings Avoiding 21

Difficulty: 1900 4000 ms 128 MB

combinatorics kmp matrix-exponentiation

Count the strings of length N over {0, 1, 2} with no contiguous occurrence of 21, modulo 10⁹+7.

Input: one integer N.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

2

8

3

21

1

3

Read the Editorial