Avoid 11 and 000

Difficulty: 2100 4000 ms 128 MB

combinatorics aho-corasick matrix-exponentiation

Count the strings of length N over {0, 1} containing NONE of the substrings 11, 000, modulo 10⁹+7.

Input: one integer N.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

2

3

3

4

1

2

Read the Editorial