Input

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

Output

$\text{Fib}(n)$ $\text{modulo}$ $m$

My Doubts

For Example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\text{fib}(7) \text{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 $\text{Fib}(n) \text{mod} m$?

Input

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

Output

$\text{Fib}(n)$ $\text{modulo}$ $m$

My questions

For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\text{fib}(7)$ $\text{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 $\text{Fib}(n)$ $\text{mod } m$?

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?

Input

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

Output

$\text{Fib}(n)$ $\text{modulo}$ $m$

My Doubts

For Example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\text{fib}(7) \text{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 $\text{Fib}(n) \text{mod} m$?