题目背景

强烈推荐新用户必读帖。

不熟悉算法竞赛的选手请看这里：

算法竞赛中要求的输出格式中， 不能有多余的内容 ， 这也包括了“请输入整数 \(\bm a\) 和 \(\bm b\)” 这一类的提示用户输入信息的内容 。若包含了这些内容，将会被认为是 Wrong Answer，即洛谷上的 WA。在对比代码输出和标准输出时，系统将忽略每一行结尾的空格，以及最后一行之后多余的换行符。

若因此类问题出现本机（看起来）AC，提交 WA 的现象，请勿认为是洛谷评测机出了问题，而是你的代码中可能存在多余的输出信息。用户可以参考在题目末尾提供的代码。

另外 请善用应用中的在线 IDE 功能 ，以避免不同平台的评测中所产生的一些问题。

还有一点很重要的是，请不要在对应的题目讨论区中发布自己的题解，请发布到题解区域中，否则将处以删除或禁言的处罚。若发现无法提交题解则表明本题题解数量过多，仍不应发布讨论。

题目描述

输入两个整数 \(a, b\) 。输出 \(a\) 阶 \(Sam\) 的数量 \(ans\)。

由于结果可能会很大，所以你只需要输出 \(ans\bmod b\) 即可。

\(Sam\) 数具有以下特征：

相邻两位的数字之差不超过 \(2\) 。一个 \(k\) 位 \(Sam\) 数称之为 \(k\) 阶 \(Sam\) 数。

注意

1. Pascal 使用 integer 会爆掉哦！
2. 有负数哦！
3. C/C++ 的 main 函数必须是 int 类型，而且 C 最后要 return 0。这不仅对洛谷其他题目有效，而且也是 NOIP/CSP/NOI 比赛的要求！

好吧，同志们，我们就从这一题开始，向着大牛的路进发。

任何一个伟大的思想，都有一个微不足道的开始。

输入格式

两个以空格分开的整数。

输出格式

一个整数。

样例 #1

样例输入 #1

4 1000000007

样例输出 #1

867

样例 #2

样例输入 #2

114 514

样例输出 #2

147

提示

对于 \(30\%\) 的数据，\(1 \le a,b \le 10^6\)。

对于 \(60\%\) 的数据，\(1 \le a,b \le 10^{12}\)。

对于 \(100\%\) 的数据，\(1 \le a,b \le 10^{18}\)。

保证 \(1 \le ans \mod \; b \le 10^{18}\)。