题目描述

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

现在问题很简单，输入$\red{ n }$和$\red{ m}$，求$\red{ \{f_n\} }$的前$\red{ n }$项和$\red{ S_n\bmod m}$。

输入格式

输入$\red{ n,m}$。

输出格式

输出前 $\red n$项和$\red{ S_n\bmod m}$。

样例

输入样例

5 1000

输出样例

12

数据范围与提示

对于$\red{ 100\% }$的数据，$\red{ 1\le n \le 2\times 10^9}$, $\red{1\le m \le 10^9+10}$。