Tổng Fibonaci

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Xét dãy số Fibonacci \({Fn}\) theo định nghĩa:

  • \(𝐹_0=𝐹_1=1\)
  • \(𝐹_n=𝐹_{n-1}+𝐹_{n-2}\ ∀𝑛>1\)

Yêu cầu: Cho số \(𝒏\), hãy tính tổng \(𝑆=𝐹_0+𝐹_1+𝐹_2+⋯+𝐹_𝑛\) và đưa ra số dư của \(S\) chia cho (\(10^9+7\)).

Input

  • Chỉ một dòng duy nhất ghi số nguyên dương \(n\) (\(𝑛≤10^{15}\)).

Output

  • Ghi một số nguyên \(S\) – số dư tìm được.

Example

Test 1

Input 
3
Output 
7
Note
  • \(S = 1+1+2+3\)

Test 1

Input 
5
Output 
20
Note
  • \(S = 1+1+2+3+5+8\)

Nguồn: CĐ DHBB

Bình luận