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

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

题目描述

大家都知道 Fibonacci 数列吧,$f\_1=1,f\_2=1,f\_3=2,f\_4=3,\\dots,f\_n=f\_{n-1}+f\_{n-2}$ 。

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

输入

输入 n,mn,m

输出

输出 f_nbmodmf\_n \\bmod m

样例

5 1000
5

提示

数据范围与提示:

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

来源

一本通在线评测