Last Digits of a Huge Fibonacci Number

Create a function that takes a number n and returns the last four digits of nth Fibonacci number.

In this challenge, the given number n may be huge (billions or so). Hence an algorithm looping for n iterations will not fit into the allotted time. Therefore you have to find out the algorithm which finds the answer in O(log n) time.

Examples

fibonacci(6) ➞ 8

fibonacci(10) ➞ 55

fibonacci(10000000) ➞ 6875

fibonacci(12345678901) ➞ 7401

Notes

The Fibonacci numbers are defined as follows:

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