Description

佳佳对数学，尤其数列十分感兴趣，在研究Fibonacci之后，他创造出许多稀奇古怪的数列。如求S(n)表示Fibonacci数列前n项和对m取模之后的值，即S(n)=(F1+F2+...+Fn)mod m，F1=F2=1。可是这对佳佳来说还是小菜一碟。终于，他找到一个自己解决不了的数列。T(n)表示Fibonacci数列前n项变形后的和对m取模之后的值，即T(n)=(F1+2×F2+3×F3+...+n×Fn)mod m，F1=F2=1。

Format

Input

第一行，包含两个整数n和m。1<=n,m<=2^31-1。

Output

共一行，T(n)的值。

Sample 1

Input

5 5

Output

1

【样例解释】
T(5)=（1+2×1+3×2+4×3+5×5）mod 5=1 。

Limitation

1s, 128MiB for each test case.
30%的数据 1<=n<=1000;
60%的数据 1<=m<=1000;
100%的数据 1<=n,m<=2^31-1;