Dãy Fibonacci

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

• \(F(1) = 1\)
• \(F(2) = 1\)
• \(F(n) = F(n-1) + F(n-2)\) với \(n > 2\)

Cho số nguyên \(n\), hãy tính \(F(n) \mod 10^9 + 7\).

Input

Một số nguyên \(n\) (\(1 \le n \le 10^{18}\)).

Output

In ra \(F(n) \mod 10^9 + 7\).

Ví dụ

Input:

10

Output:

55

Gợi ý: Dùng nhân ma trận để tính Fibonacci trong \(O(\log n)\).