Narayana's Cows Modulo

Difficulty: 1750 4000 ms 128 MB

math matrix-exponentiation

The sequence obeys N(0)=N(1)=N(2)=1 and N(n)=N(n−1)+N(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

4

0

1

Read the Editorial