佳佳的 Fibonacci

题号：NC50581
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

佳佳对数学，尤其对数列十分感兴趣。在研究完Fibonacci数列后，他创造出许多稀奇古怪的数列。例如用S(n)表示Fibonacci前n项和 $\bmod m$ 的值，即 $S(n)=(F_1+F_2+...+F_n) \bmod m$ ，其中 $F_1=F_2=1,F_i=F_{i-1}+F_{i-2}$ 。可这对佳佳来说还是小菜一碟。
终于，她找到了一个自己解决不了的问题。用 $T(n)=(F_1+2F_2+3F_3+...+nF_n) \bmod m$ 表示Fibonacci数列前n项变形后的和 $\bmod m$ 的值。
现在佳佳告诉你了一个n和m，请求出T(n)的值。

输入描述:

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

输出描述:

仅一行，T(n)的值。

示例1

输入

复制

5 5

输出

复制

说明

备注:

对于的数据，；
对于的数据，；
对于的数据，。