Row Coloring, 5 Colors

Difficulty: 1300 4000 ms 128 MB

combinatorics

Count the ways to color a row of N cells with 5 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

5

2

20

3

80

Read the Editorial