Doubling Plus Carry

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

A quantity follows Q(0)=1, Q(1)=3, Q(n)=3Q(n−1)−Q(n−2). Print Q(N) modulo 10⁹+7.

Input: one integer N.

Output: the value modulo 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

5

144

1

3

Read the Editorial