J19 习题-2 Fibonacci前 n 项和

题目描述

大家都知道 $\rm Fibonacci$ 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,...,f_n=f_{n-1}+f_{n-2}$。

现在问题很简单，输入 $n$ 和 $m$ ，求 $f_n$ 的前 $n$ 项和 $S_n~mod~m$。

输入格式

输入$n,m$ 。

输出格式

输出 $f_n~mod~m$。

样例输入

5 1000

样例输出

12

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$0\leq n \leq 2 \times 10^9,1\leq m \leq 10^9+10$。