题目描述

大家都知道Fibonacci数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n-1}+f_{n-2}$。 现在问题很简单，输入n和m，求$\{f_n \}$的前n项和$S_n \bmod m$。

输入描述

输入n,m。

输出描述

输出前n项和$S_n \bmod m$。

示例1

输入

5 1000

输出

12

备注

输入样例 #2

10 1000

输出样例 #2

143

输入样例 #3

50 10007

输出样例 #3

337

数据范围

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