题目描述

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

现在问题很简单，输入 $n$ 和 $m$，求 $f\_n\\bmod m$。

输入

输入 $n,m$。

输出

输出 $f\_n \\bmod m$。

样例

5 1000

5

提示

数据范围与提示：

对于 100% 的数据， $1\\le n \\le 2 × 10^9, 1\\le m \\le 10^9+10$。

来源

一本通在线评测