当前没有测试数据。

Background

Special for beginners, ^_^

Description

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

Format

Input

输入 $n$ 和 $m$。

Output

输出 $f_n\bmod m$ 。

Samples

input

5 1000

ouput

5

Tips

数据范围与提示：

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