题目描述

大家都知道 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_nmodm$。

输入

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

输出

输出前 $n$项和 $S_nmodm$的值。

5 1000

12

提示

$1≤n≤2000000000,$

$1≤m≤1000000010$