Xét dãy số Fibonacci {Fn} theo định nghĩa:
F0=F1=1
Fn=Fn-1+Fn-2 ∀n>1
Cho số n, hãy tính tổng S=F0+F1+F2+⋯+Fn và đưa ra số dư của S chia cho (109+7).
Dữ liệu: gồm một dòng duy nhất ghi số nguyên dương n(n≤1015).
Kết quả: một số nguyên – số dư tìm được.
| INPUT | OUTPUT |
| 3 | 7 |
| 5 | 20 |