126. N-th Fibonacci Modulo
MediumFast DoublingMatrix Power
F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2). Print F(n) mod 10⁹ + 7.
Input format
A single integer n.
Output format
F(n) mod 10⁹ + 7
Example 1
Input
10
Output
55
Example 2
Input
0
Output
0
Constraints
0 ≤ n ≤ 10¹⁸
Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.
Loading the MyLoginn IDE…