Avoid the Set {ab, bc, ca}

Difficulty: 2400 4000 ms 128 MB

combinatorics aho-corasick matrix-exponentiation

Count the strings of length N over {a, b, c} that contain none of ab, bc, ca as a substring, modulo 10⁹+7.

Input: one integer N.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

1

3

2

6

4

24

Read the Editorial