#1495. 「一本通 6.5 例 2」Fibonacci 第 n 项

「一本通 6.5 例 2」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,\dots,f_n=f_{n-1}+f_{n-2}

现在问题很简单,输入 nnmm,求 fnmodmf_n\bmod m

输入格式

输入 n,mn,m

输出格式

输出 fnmodmf_n \bmod m

样例

5 1000
5

数据范围与提示

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