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