Cho số nguyên không âm nnn. Hãy tính số Fibonacci thứ nnn theo modulo 109+710^9 + 7109+7.
Quy ước F0=0F_0 = 0F0=0, F1=1F_1 = 1F1=1, Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn=Fn−1+Fn−2.
Một dòng chứa số nguyên không âm nnn.
0≤n≤1060 \le n \le 10^60≤n≤106
In ra Fn mod (109+7)F_n \bmod (10^9 + 7)Fnmod(109+7).
Ví dụ:
Đầu vào:
10
Đầu ra:
55
Giải thích:
Đang tải editor...