Dãy số Fibonacii được định nghĩa như sau:

• \(f_0=0\)

• \(f_1=1\)

• \(f_i=f_(i-1)+f_(i-2)\)

Yêu cầu: Cho số nguyên dương \(n\). Tính \(f_n\). Kết quả lấy số dư khi chia \(f_n\) cho \(10^9+7\).

Input

• Gồm một dòng chứa số nguyên \(n (0≤n≤10^{18} ).\)

Output

• Ghi kết quả \(f_n\) lấy lấy số dư khi chia \(f_n\) cho \(10^9+7\).

Ràng buộc

• Subtask 1: 40% test với \(n≤10^6\).

• Subtask 2: 60% test với \(n≤10^18\)

Sample Input

10

Sample Output

55