No Three in a Row

Difficulty: 2000 4000 ms 128 MB

dp combinatorics matrix-exponentiation

Count the strings of length N over {0,1,2} in which no value appears three times consecutively, modulo 10⁹+7.

Input: one integer N.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

1

3

2

9

3

24

Read the Editorial