Description

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$.

Input Format

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

Output Format

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

5
1000000007

5

10
1000000007

55

Hint

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

Translated by ChatGPT 5