#406. Fibonacci 前 n 项和

Fibonacci 前 n 项和

题目描述

大家都知道 Fibonacci 数列吧,f1=1,f2=1,f3=2,f4=3,,fn=fn1+fn2f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n-1}+f_{n-2}

现在问题很简单,输入 nnmm,求 {fn}\{f_n\} 的前 nn 项和 SnmodmS_n\bmod m

输入格式

输入 n,mn,m

输出格式

输出前 nn 项和 SnmodmS_n\bmod m

样例

5 1000
12

数据范围与提示

对于 100%100\% 的数据, 1n2×109,1m109+101\le n \le 2\times 10^9, 1\le m \le 10^9+10