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 >1)\)

Yêu cầu: 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\).

Input

• Gồm 1 dòng chứa số nguyên \(n\).

Output

• Ghi ra tổng \(S\) tìm được khi chia lấy dư cho \(10^9+7\)

Ràng buộc

• Subtask 1: 50% test với \(n ≤ 10000\)

• Subtask 2: 50% test với \(1000 < n ≤ 10^{15}\)

Sample Input

3

Sample Output

7

Tag: NMT