A Zoho Analytics computation may need to evaluate very large indexed sequence values without iterating through every preceding term. Given n and a positive modulus, return the nth Fibonacci number modulo that modulus using an algorithm faster than linear time.
The Fibonacci sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n >= 2.
Use the fast-doubling identities:
F(2k) = F(k) * (2F(k + 1) - F(k))F(2k + 1) = F(k)^2 + F(k + 1)^2Implement fibonacci_mod(n, mod), where n and mod are integers. Return an integer equal to F(n) % mod. The algorithm must run in O(log n) time.
def fibonacci_mod(n, mod):