Dãy Số Tribonacci

Buổi 59 — Lũy thừa ma trận
Points
26
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Dãy Tribonacci được định nghĩa: $T_0 = 0, T_1 = 1, T_2 = 1$, và $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ với mọi $n \ge 3$. Cho số nguyên không âm $N$, hãy tính $T_N \bmod (10^9 + 7)$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $N$ ($0 \le N \le 10^{18}$).

Dữ liệu ra

Một số nguyên duy nhất là $T_N \bmod (10^9 + 7)$.

Ví dụ
Input Output
4 4
10 149
Giới hạn
  • $0 \le N \le 10^{18}$
Draft saved