Fibonacci siêu lớn bằng nhân ma trận

Buổi 05 — Hàm & Đệ quy Mathematics
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho số nguyên không âm $N$ rất lớn. Hãy tính số Fibonacci thứ $N$ ($F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$) chia lấy dư cho $10^9 + 7$ bằng phương pháp lũy thừa ma trận đệ quy.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $N$.

Dữ liệu ra

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

Ví dụ
Input Output
10 55
1000000000 21
Giới hạn

$0 \le N \le 10^{18}$.

Draft saved