题目描述

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

示例1

输入

5 1000

输出

5

备注

输入样例 #2

10 1000

输出样例 #2

55

输入样例 #3

50 10007

输出样例 #3

4803

数据范围

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