佳佳的 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;