Sequence g=1a+7b (g0=g1=1)

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

The sequence has g(0)=g(1)=1 and g(n)=1g(n−1)+7g(n−2). Print g(N) modulo 10⁹+7.

Input: one integer N.

Output: g(N) mod 10⁹+7.

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

4

71

0

1

1

1

Read the Editorial