Chỉ Số Fibonacci

Dãy Fibonacci (F_i) được đánh số từ $0$ và được xác định bởi $F_0=0,F_1=1$. Với mọi $i\ge 2$, ta có $F_i=F_{i-1}+F_{i-2}$.

Cho chỉ số $n$, hãy tính $F_n$ theo modulo $1000000007$.

Input

• Input gồm đúng một số nguyên $n$ - chỉ số cần tính.

Output

• In $F_n$ theo modulo $1000000007$.

Constraints

• $0\le n\le 10^{18}$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 2000$.
• Subtask $2$ ($50\%$ số điểm): không có giới hạn bổ sung.

Example

10

55