Description

Everyone knows the Fibonacci sequence, right? $f_1=1$, $f_2=1$, $f_3=2$, $f_4=3$, $\dots$, $f_n=f_{n-1}+f_{n-2}$.

Now the problem is simple: given $n$ and $m$, compute $f_n \bmod m$.

Input Format

Input $n$ and $m$.

Output Format

Output $f_n \bmod m$.

Sample 1

5 1000

5

Constraints & Hints

For $100\%$ of the data, $1\le n \le 2\times 10^9$, $1\le m \le 10^9+10$.