Últimos dígitos de un número de Fibonacci enorme

Crea una función que reciba un número n y devuelva los últimos cuatro dígitos del número de Fibonacci en la posición n.

En este desafío, el número n dado puede ser enorme (del orden de miles de millones). Por lo tanto, un algoritmo que itere n veces no terminará dentro del tiempo asignado. Por eso, debes determinar el algoritmo que encuentre la respuesta en O(log n).

Ejemplos

fibonacci(6) ➞ 8

fibonacci(10) ➞ 55

fibonacci(10000000) ➞ 6875

fibonacci(12345678901) ➞ 7401

Notas

Los números de Fibonacci se definen de la siguiente manera:

f(0) = 0, f(1) = 1, and f(i) = f(i−1) + f(i−2)