P4000 Fibonacci Sequence

Everyone knows the Fibonacci sequence is defined by the following properties: - $f_0 = 0$. - $f_1 = 1$. - $f_n = f_{n-1} + f_{n-2}$ ($n \geq 2$ and $n$ is an integer). Please compute the value of $f_n \bmod p$.

- Line 1: An integer $n$. - Line 2: An integer $p$.

- Line 1: The value of $f_n \bmod p$.

For $100\%$ of the testdata, $0 \leq n \leq 10^{30000000}$, $1 \leq p < 2^{31}$. Translated by ChatGPT 5