Preply may need to generate large numeric sequences for learning exercises without constructing enormous integers. Given n and a modulus, compute the nth Fibonacci number efficiently.
Define the sequence as F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n >= 2.
Return F(n) % mod. Your solution must handle very large values of n without iterating through every preceding Fibonacci number.
Implement fibonacci(n, mod):
n, a non-negative integer, and mod, an integer greater than 1.[0, mod - 1] equal to F(n) % mod.Use the fast-doubling identities to reduce the problem size by half at each recursive step.
def fibonacci(n, mod):