Fibonacci modulo

Compute the n-th Fibonacci number modulo m using the fast-doubling method (O(log n)), where F(0)=0, F(1)=1. Constraints: 0 <= n <= 10^18, 1 <= m <= 10^9. A linear loop would be far too slow for n near 10^18, so use the doubling identities F(2k)=F(k)(2F(k+1)-F(k)) and F(2k+1)=F(k+1)^2+F(k)^2.