Description

Jiajia is very interested in mathematics, especially in sequences. After studying the Fibonacci sequence, she has created many peculiar sequences. For example, let $S(n)$ denote the sum of the first $n$ terms of the Fibonacci sequence modulo $m$, i.e., $S(n)=(F_1+F_2+...+F_n)\bmod m$, where $F_1=F_2=1$ and $F_i=F_{i-1}+F_{i-2}$. However, this is still a piece of cake for Jiajia.

Finally, she encountered a problem she couldn't solve. Let $T(n)=(F_1+2F_2+3F_3+...+nF_n)\bmod m$ represent the modified sum of the first $n$ terms of the Fibonacci sequence modulo $m$.

Now, Jiajia gives you two integers $n$ and $m$, and asks you to compute the value of $T(n)$.

Input Format

The input consists of a single line containing two integers $n$ and $m$, separated by a space.

Output Format

Output a single line containing the value of $T(n)$.

Sample 1

$T(5)=(1+2\times 1+3\times 2+4\times 3+5\times 5)\bmod 5=1$

5 5

1

Constraints and Hints

For $30\%$ of the data, $1\le n \le 1000$;

For $60\%$ of the data, $1\le m \le 1000$;

For $100\%$ of the data, $1\le n,m \le 2^{31}-1$.