Input

Integers 'n' (up to 10^14) and 'm'(up to 10^3)

Output

Fib(n) modulo m

My Doubts

For Example : Why fib(n=2015) mod 3 is equivalent to fib(7) mod 3? (for 𝑚 = 3 the period is 01120221 and has length 8 and 2015=251*8 + 7)

In general, after getting the remainder sequence, how(mathematical proof) it is used for computing Fib(n) mod m?