题目描述
大家都知道 Fibonacci 数列吧，
f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n-1}+f_{n-2}
f1
=1,f2
=1,f3
=2,f4
=3,…,fn
=fn−1
+fn−2
。
现在问题很简单，输入
n
n 和
m
m，求
\{f_n\}
{fn
} 的前
n
n 项和
S_n\bmod m
Sn
modm。
输入
输入
n,m
n,m。
输出
输出前
n
n 项和
S_n\bmod m
Sn
modm。
样例输入
5 1000
样例输出
12
提示
数据范围与提示
对于
100\%
100% 的数据，
1\le n \le 2\times 10^9, 1\le m \le 10^9+10
1≤n≤2×109,1≤m≤109+10。
来源/分类
ybttg 矩阵