题目描述

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2 。

现在问题很简单，输入 n 和 m ，求 {fn} 的前 n 项和 Snmodm 。

输入格式

输入 n,m 。

输出格式

输出前 n 项和 Snmodm 。

样例

5 1000

12

提示

数据范围与提示：

对于 100% 的数据， 1≤n≤2×109,1≤m≤109+10 。