佳佳的 Fibonacci

佳佳的 Fibonacci

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;