Walks on a Path of 6

Difficulty: 1800 4000 ms 128 MB

graphs matrix-exponentiation

Count the closed walks of length N that start and end at vertex 1 in a path 1-2-3-4-5-6, modulo 10⁹+7.

Input: one integer N.

Output: the number of closed walks mod 10⁹+7.

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

2

1

0

1

Read the Editorial