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

时间限制：$1.5s$，空间限制：$512mb$

题目描述

在$3202$年，小明发明了一个自动AC机。这个机器特别厉害，可以做任何题目。

可惜这个机器还在验证正确性的阶段，如果通过了验证阶段，才能说明这个机器真的管用。

今天，小明给这个机器投喂了这样一道题目。

小明有一个数字，这个数字$f$在第$1$天的值$f_1$是$1$，第$2$天的值$f_2$是$1$，第$i(i\geq 3)$天的值$f_i$是$(f_{i-1}+f_{i-2})\mod P$。

那么，第$n$天的值是多少呢？

输入格式

第一行输入两个正整数$n,P$。

输出格式

输出一个数字表示答案。

样例输入 #1

10 998244353

样例输出 #1

55

样例解释 #1

前$10$项分别是$1,1,2,3,5,8,13,21,34,55$。

样例输入 #2

998244353 997

样例输出 #2

950

数据范围

一共$20$个测试点。

对于测试点1-8 ：$n\leq 10^5$。

对于测试点9-10 ：$n\leq 10^9$。（提示：小常数$1e9$的做法是可以过的）

对于测试点11-17 ：$P\leq 1000$。

对于测试点18-20 ：无特别限制。

对于100%的数据：$n\leq 10^{12},3\leq P\leq 998244353$。