Compound with Memory

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

A value follows V(0)=1, V(1)=2, V(n)=2V(n−1)+2V(n−2). Print V(N) modulo 10⁹+7.

Input: one integer N.

Output: the value modulo 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

5

120

1

2

Read the Editorial