MathMatrix ExponentiationDivide and Conquer
Find the n-th Fibonacci number (F(0) = 0, F(1) = 1, F(k) = F(k - 1) + F(k - 2)) modulo 1,000,000,007, where n can be as large as 10^18. A loop over n steps would never finish.
Input
A single integer n.
Output
Print F(n) mod 1000000007.
Constraints
0 <= n <= 10^18
Example 1
Input
10
Output
55
F(10) = 55.
Example 2
Input
100
Output
687995182
F(100) mod 1000000007 = 687995182.