该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

$S_n$ 表示 Fibonacci 前 $n$ 项和 $\mod m$ 的值，即 $S_n=(F_1+F_2+ \dots +F_n)\bmod m$，其中 $F_1=F_2=1, F_i=F_{i-1}+F_{i-2}$。可这对佳佳来说还是小菜一碟。

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

已知： $n$ 和 $m$，求 $T_n$ 的值。

【输入格式】

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

【输出格式】

仅一行， $T_n$ 的值。

5 5

1

【样例解释】

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

【数据范围与提示】

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

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

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