Row Coloring, 4 Colors

Difficulty: 1300 4000 ms 128 MB

combinatorics

Count the ways to color a row of N cells with 4 colors so that no two adjacent cells share a color, modulo 10⁹+7.

Input: one integer N.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

1

4

2

12

3

36

Read the Editorial