1304

1304. 佳佳的斐波那契

题目

佳佳对数学，尤其对数列十分感兴趣。

在研究完 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 \le n,m \le 2^{31}-1$

输入样例：

5 5

输出样例：

1

样例解释

$T(5) = (1 + 2 \times 1 + 3 \times 2 + 4 \times 3 + 5 \times 5) \bmod 5 = 1$

题解