#945. Fibonacci mod 10⁹+7 (big n)
You get n (n ≤ 10¹⁸). Find Fₙ mod 1000000007 (F₀ = 0, F₁ = 1). Hint: use matrices or the fast doubling method.
### Input
One integer n.
### Output
A number.
Examples
Input
22363955353728191
Output
384449992
Input
9292445420288466
Output
334156964
💡 You can solve it with Python, JavaScript or blocks. Read the input line by line with input(). Don't print a question (like input("Number: ")). Print exactly what the output asks for, nothing more.