Fibonacci modulo m
Your task
Return the n-th Fibonacci number modulo m, where F(0) = 0 and F(1) = 1, for n that can be very large (up to 10^18). Linear iteration is too slow, so use 2x2 matrix exponentiation of [[1,1],[1,0]] by fast (binary) exponentiation, taking every product modulo m. Return 0 when m == 1.
Examples
fib_mod(n: int, m: int) -> intExample 1
Input
fib_mod(10, 1000)Output
55