问题 R: 斐波那契前 n 项和

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

现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Sn mod m。

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

输出前 n 项和 Sn mod m 的值。

数据范围

1≤n≤2000000000
1≤m≤1000000010

输入样例：

5 1000

输出样例：

12