4043佳佳的 Fibonacci

4043   佳佳的 Fibonacci

题目描述

佳佳对数学，尤其对数列十分感兴趣。在研究完 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) 的值。

输入格式:

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

输出格式:

仅一行，T(n) 的值。
输入样例 复制 
5 5
输出样例 复制 
1

说明

样例解释
T(5)=(1+2×1+3×2+4×3+5×5)mod5=1
数据范围与提示：
对于 30% 的数据，1≤n≤1000   ；
对于 60% 的数据，1≤m≤1000   ；
对于 100% 的数据，1≤n,m≤231−1  。
3
187
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型矩阵
难        度