I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{1000}$ and $k<10^9$), where I compute fib[n] % k. What is a good FAST way of computing this?

I realize that the resulting series is periodic, just not sure how to find it efficiently.