题目描述

佳佳对数学，尤其对数列十分感兴趣。在研究完 $\red{Fibonacci}$ 数列后，他创造出许多稀奇古怪的数列。例如用$\red{ S(n) }$表示$\red{ Fibonacci }$前$\red{ n }$项和$\red{ \bmod m }$的值，即 $\red{S(n)=(F_1+F_2+...+F_n)\bmod m}$，其中$\red{ F_1=F_2=1, F_i=F_{i-1}+F_{i-2}}$。可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。用$\red{ T(n)=(F_1+2F_2+3F_3+...+nF_n)\bmod m }$表示$\red{ Fibonacci}$ 数列前$\red{ n }$项变形后的和$\red{ \bmod m }$的值。

现在佳佳告诉你了一个$\red{ n }$和$\red{ m}$，请求出$\red{ T(n)}$ 的值。

输入格式

输入数据包括一行，两个用空格隔开的整数$\red{ n,m}$。

输出格式

仅一行，$\red{T(n)}$ 的值。

样例

输入样例

5 5

输出样例

1

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

数据范围与提示

对于$\red{ 30\% }$的数据，$\red{1\le n \le 1000}$；

对于$\red{ 60\% }$的数据，$\red{1\le m \le 1000}$；

对于$\red{ 100\% }$的数据，$\red{1\le n,m \le 2^{31}-1}$。