Sequence r=5a+4b (r0=0,r1=1)

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

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

Input: one integer N.

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

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

5

941

0

0

1

1

Read the Editorial