【题目描述】

大家都知道 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$。

【来源】

一本通在线评测