该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：fibn.in 输出文件：fibn.out

求斐波那契数列第 $N$ 项对 $M$ 取模的值。

本题斐波那契定义：

- $F_1 = 0$

- $F_2 = 1$

- $F_n = F_{n-1} + F_{n-2}$

输入格式

一行两个整数 $N, M$。

输出格式

输出 $F_N \bmod M$。

样例

样例 1

10 20

14

样例说明：

$F_{10}=34$，$34 \bmod 20 = 14$

样例 2

20 1000

181

样例 3

30 17

13

数据范围

对于 100% 的数据，$10 \le N \le 5\times10^6$，$2 \le M < 2^{31}$。