Description

佳佳对数学，尤其对数列十分感兴趣。在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。例如用s(n)表示 Fibonacci 前 n项和mod m 的值，即s(n)=(f1+f2+,+...+fn) mod m ，其中f1=f2=1,fi=fi-1+fi-2 。可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。用T(n)=(f1+2f2+3f3+...+nfn) mod m表示 Fibonacci 数列前n项变形后的和 mod m的值。

现在佳佳告诉你了一个n 和m，请求出T(n) 的值。

Input Format

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

Output Format

仅一行，T(n) 的值。

Sample

输入

5 5

输出

1

T(5)=(1+21+32+43+55) mod 5=1

Hint

对于30% 的数据，1<=n<=1000；

对于60%的数据，1<=m<=1000；

对于100%的数据，1<=n,m<=2^31-1。