Xét dãy số Fibonacci {Fn} theo định nghĩa:
𝐹0=𝐹1=1
𝐹n=𝐹n-1+𝐹n-2 ∀𝑛>1
Cho số 𝒏, hãy tính tổng 𝑆=𝐹0+𝐹1+𝐹2+⋯+𝐹𝑛 và đưa ra số dư của S chia cho (109+7).
Dữ liệu:
Chỉ một dòng duy nhất ghi số nguyên dương n (𝑛≤1015).
Kết quả:
Ghi một số nguyên – số dư tìm được.
Input
3
Output
7
Input
5
Output
20
Nguồn: CĐ DHBB