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

• \(F_0 = 0\)
• \(F_1 = 1\)
• \(F_n = F_{n-2} + F_{n-1}\) (với \(n \ge 2\))

Cho số nguyên dương \(n\), hãy tính giá trị \(F_{F_n} \pmod{10^9 + 7}\).

Input

• Một dòng duy nhất chứa số nguyên \(n\).

Output

• In ra một số nguyên duy nhất là kết quả của \(F_{F_n} \pmod{10^9 + 7}\).

Constraints

• \(0 \le n \le 10^{18}\)

Example

10

583861472