题目描述

佳佳对数学，尤其对数列十分感兴趣。在研究完Fibonacci数列后，他创造出许多稀奇古怪的数列。例如用S(n)表示Fibonacci前n项和$\bmod m$的值，即$S(n)=(F_1+F_2+...+F_n) \bmod m$，其中$F_1=F_2=1,F_i=F_{i-1}+F_{i-2}$。可这对佳佳来说还是小菜一碟。 终于，她找到了一个自己解决不了的问题。用$T(n)=(F_1+2F_2+3F_3+...+nF_n) \bmod m$表示Fibonacci数列前n项变形后的和$\bmod m$的值。 现在佳佳告诉你了一个n和m，请求出T(n)的值。

输入描述

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

输出描述

仅一行，T(n)的值。

示例1

输入

5 5

输出

1

说明

$T(5)=(1+2 \times1+3 \times2+4 \times3+5 \times5) \bmod5=1$

备注

输入样例 #2

1 321

输出样例 #2

1

输入样例 #3

34 107

输出样例 #3

3

数据范围

对于$30 \%$的数据，$1 \leq n \leq1000$； 对于$60 \%$的数据，$1 \leq m \leq1000$； 对于$100 \%$的数据，$1 \leq n,m \leq 2^{31}-1$。