Tribonacci Modulo

Difficulty: 1750 4000 ms 128 MB

matrix-exponentiation

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

Input: one integer N.

Output: the value modulo 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

4

4

0

0

1000000000000000000

926781415

Read the Editorial