1303

1303. 斐波那契前 n 项和

题目

大家都知道 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 \bmod m$。

输入格式

共一行，包含两个整数 $n$ 和 $m$。

输出格式

输出前 $n$ 项和 $S_n \bmod m$ 的值。

数据范围

$1 \le n \le 2000000000$,

$1 \le m \le 1000000010$

输入样例：

5 1000

输出样例：

12

题解