With F0 = 0, F1 = 1 and F(n) = F(n-1) + F(n-2), write fibonacci(n: int) -> int returning F(n) mod 1_000_000_007 for 0 ≤ n ≤ 10^18.
Iterating n times is out of the question; aim for O(log n) arithmetic operations.
fibonacci(0) # 0
fibonacci(10) # 55
fibonacci(50) # 12586269025 mod p = 586268941
| 1 1 |^n | F(n+1) F(n) |
| 1 0 | = | F(n) F(n-1) |
so raise the matrix to the n-th power by repeated squaring, reducing mod p after each multiplication. (The "fast doubling" formulas for F(2k) and F(2k+1) work too.)
Show hint
The step (F(k+1), F(k)) → (F(k+2), F(k+1)) is multiplication by a fixed 2×2 matrix, and in fact