#T1644. 「一本通 6.5 例 4」佳佳的 Fibonacci

「一本通 6.5 例 4」佳佳的 Fibonacci

题目描述

佳佳对数学,尤其对数列十分感兴趣。在研究完 Fibonacci 数列后,他创造出许多稀奇古怪的数列。例如用 S(n)S(n) 表示 Fibonacci 前 nn 项和 bmodm\\bmod m 的值,即 S(n)=(F_1+F_2+...+F_n)bmodmS(n)=(F\_1+F\_2+...+F\_n)\\bmod m,其中 F_1=F_2=1,F_i=F_i1+F_i2F\_1=F\_2=1, F\_i=F\_{i-1}+F\_{i-2} 。可这对佳佳来说还是小菜一碟。

终于,她找到了一个自己解决不了的问题。用 T(n)=(F_1+2F_2+3F_3+...+nF_n)bmodmT(n)=(F\_1+2F\_2+3F\_3+...+nF\_n)\\bmod m 表示 Fibonacci 数列前 nn 项变形后的和 mod m 的值。

现在佳佳告诉你了一个 nnmm,请求出 T(n)T(n) 的值。

输入

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

输出

仅一行,T(n)T(n) 的值。

样例

5 5
1

提示

样例解释

T(5)=(1+2×1+3×2+4×3+5×5)bmod5=1T(5)=(1+2 × 1+3× 2+4× 3+5× 5)\\bmod 5=1

数据范围与提示:

对于 30% 的数据,1n10001≤n≤1000

对于 60% 的数据,1m10001≤m≤1000

对于 100% 的数据,1n,m23111≤n,m≤2^{31}−1

来源

一本通在线评测