Dãy Fibonacci được định nghĩa 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. Vì FnF_nFn rất lớn, hãy in ra Fn mod 1000000007F_n \bmod 1000000007Fnmod1000000007.
Một số nguyên không âm n.
n
0≤n≤1070 \le n \le 10^70≤n≤107
Một số nguyên là 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...