4362. 1644：【例 4】佳佳的 Fibonacci
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 佳佳对数学，尤其对数列十分感兴趣。在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。例如用 $S(n)$ 表示 Fibonacci 前 $n$ 项和 $\mod m$ 的值，即 $S(n) = (F\_1 + F\_2 + \ldots + F\_n) \mod m$，其中 $F\_1 = F\_2 = 1$, $F\_i = F\_{i-1} + F\_{i-2}$。可这对佳佳来说还是小菜一碟。 终于，她找到了一个自己解决不了的问题。用 $T(n) = (F\_1 + 2F\_2 + 3F\_3 + \ldots + nF\_n) \mod m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $\mod m$ 的值。 现在佳佳告诉你了一个 $n$ 和 $m$，请求出 $T(n)$ 的值。 ## 输入 - 输入数据包括一行，两个用空格隔开的整数 $n, m$。 ## 输出 - 仅一行，$T(n)$ 的值。 ## 输入样例 ``` 5 5 ``` ## 输出样例 ``` 1 ``` ## 提示 - 样例解释 - $T(5) = (1 + 2 \times 1 + 3 \times 2 + 4 \times 3 + 5 \times 5) \mod 5 = 1$ - 数据范围与提示： - 对于 30% 的数据，$1 \leq n \leq 1000$； - 对于 60% 的数据，$1 \leq m \leq 1000$； - 对于 100% 的数据，$1 \leq n, m \leq 2^{31} - 1$。 ---