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

• \(F_0=F_1=1\)
• \(F_n=F_{n-1}+F_{n-2}\) \((n \gt 1)\)

Cho số \(n\) hãy tính tổng \(S=F_0+F_1+F_2+...+F_n\) và đưa ra số dư của \(S\) chia cho \((10^9 + 7)\)

Dữ liệu vào

• Số nguyên \(n\) \((n \le 10^{15})\)

Dữ liệu ra

• Số dư tìm được

Input 1

3

Output 1

7

Input 2

5

Output 2

20