Strings with an Even Number of Zeros

Difficulty: 1800 4000 ms 128 MB

combinatorics matrix-exponentiation

Count the strings of length N over {0, 1, 2} that contain an EVEN number of 0s, modulo 10⁹+7.

Input: one integer N.

Output: the count modulo 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

1

2

2

5

3

14

Read the Editorial