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

3    

7

5    

20

Nguồn: CĐ DHBB