Description

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

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

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

Input Format

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

Output Format

仅一行，T(n) 的值。

Sample

输入

5 5

输出

1

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

Hint

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

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

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