Fibonacci modulo m

Write codeHard30 min

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) -> int
Example 1
Inputfib_mod(10, 1000)
Output55