大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2f_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。
现在问题很简单，输入 nnn 和 mmm，求 fn{f_n}fn 的前 nnn 项和 Sn mod mS_n \bmod mSnmodm。
共一行，包含两个整数 nnn 和 mmm。
输出前 nnn 项和 Sn mod mS_n \bmod mSnmodm 的值。
1≤n≤20000000001 \le n \le 20000000001≤n≤2000000000,
1≤m≤10000000101 \le m \le 10000000101≤m≤1000000010
5 1000
12
注册一个 Hydro 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 Hydro 通用账户
