Sequence h=4a+7b (h0=0,h1=1)

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

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

Input: one integer N.

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

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

5

641

0

0

1

1

Read the Editorial