Pell Numbers Modulo

Difficulty: 1700 4000 ms 128 MB

matrix-exponentiation

The Pell sequence is P(0)=0, P(1)=1, P(n)=2P(n−1)+P(n−2). Print P(N) modulo 10⁹+7.

Input: one integer N.

Output: the value modulo 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

3

5

1

1

1000000000000000000

3540480

Read the Editorial