一个探险队从 ACM-1 行星飞往地球,以研究双足物种(其代表头上甚至没有天线!)。
勇敢的先驱者们乘坐的飞碟由三部分组成。这些部分通过链条连接:第 1 个部分仅与第 2 个部分相邻,第 2 个部分与第 1 个和第 3 个部分相邻,第 3 个部分仅与第 2 个部分相邻。过渡只能在相邻部分之间进行。
飞船团队由n个外星人组成。他们每个人都有一个排名——一个从 1 到 n 的整数。所有宇航员的级别都是不同的。碟子上制定的规则规定,只有当外国人的等级比a和b部分中的所有外国人都高时,才可以从a部分移动到b部分(此外,a部分和b部分当然必须相邻)。任何外星人都需要 1 分钟的时间才能采取行动。此外,安全法规要求同一分钟船上不得有超过一名外国人移动。
外国人 A 的级别比外国人 B 的级别高,如果表示级别 A 的数字大于 B 的对应数字。
目前整个飞碟队都处于第三段。他们都需要移动到第一段。一名机组人员,即识别号为 CFR-140 的外星人,决定计算执行此任务所需的最短时间(以分钟为单位)。
帮助 CFR-140,计算出所有宇航员从第三段移动到第一段所需的最短时间(以分钟为单位)。由于这个数字可能相当大,因此以 m 为模进行计算。
输入
第一行包含两个空格分隔的整数:n 和 m (1 ≤ n, m ≤ 109) — 碟子上的外星人数量以及您应该相应打印答案的数字。
输出
打印一个数字——问题的答案以 m 为模。
示例
输入 #1
1 10
输出 #1
2
输入 #2
3 8
输出 #2
2
注意
在第一个样本中,唯一的机组成员从段 3 移动到段 2,然后从段 2 移动到段 1,没有任何问题。因此,整个搬家过程需要两分钟。
为了简要描述第二个样本中的移动,我们将使用值 $${\vec{R}}_{i}\to{\vec{j}}$$,该值对应于排名为 i 的外星人从其当前所在的段移动到段号 j。使用这些值,我们将描述第二个样本中各段之间的移动: $$R_{3} \rightarrow 2$$, $$R_{3} \rightarrow 1$$, $$R_{2} \rightarrow 2$$, $$R_{3} \rightarrow 2$$, $$R_{3} \rightarrow 3$$, $$R_{2} \rightarrow 1$$, $$R_{3} \rightarrow 2$$、$$R_{3}\rightarrow 1$$、$$R_{1}\rightarrow2$$、$$R_{3}\rightarrow 2$$、$$R_{3}\rightarrow 3$$、$$R_{2}\rightarrow 2$$、$$R_{3}\rightarrow 2$$、$$R_{3}\rightarrow 1$$、 $$R_{2}\rightarrow3$$、$$R_{3}\rightarrow 2$$、$$R_{3}\rightarrow 3$$、$$R_{1}\rightarrow 1$$、$$R_{3}\rightarrow 2$$、$$R_{3}\rightarrow 1$$、$$R_{2}\rightarrow 2$$、$$R_{3}\rightarrow 2$$, $$R_{3} \rightarrow 3$$, $$R_{2} \rightarrow 1$$, $$R_{3} \rightarrow 2$$, $$R_{3} \rightarrow 1$$;总共:外星人需要 26 步。 26 除以 8 的余数等于 2,因此该测试的答案是 2。