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 the sum of the first $n$ terms of the sequence $\{f_n\}$ modulo $m$, i.e., $S_n \bmod m$.

Input Format

Input $n$ and $m$.

Output Format

Output the sum of the first $n$ terms $S_n \bmod m$.

Sample 1

5 1000

12

Data Range and Hint

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