Padovan Numbers Modulo

Difficulty: 1750 4000 ms 128 MB

math matrix-exponentiation

The sequence obeys P(0)=P(1)=P(2)=1 and P(n)=P(n−2)+P(n−3). Print term N modulo 10⁹+7.

Input: one integer N.

Output: term N mod 10⁹+7.

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

5

3

0

1

Read the Editorial