CF226A Flying Saucer Segments

一个探险队从 ACM-1 星球飞来地球，目的是研究两足生物（据说他们甚至头上都没有天线！）。 勇敢的先驱们乘坐的飞碟由三个舱段组成，这些舱段通过一条链条连接：第 1 舱段只与第 2 舱段相邻，第 2 舱段与第 1、3 舱段相邻，第 3 舱段只与第 2 舱段相邻。只能在相邻的舱段之间移动。 飞船上共有 $n$ 个外星人，每个外星人有一个等级，是 $1$ 到 $n$ 之间的整数。所有宇航员的等级互不相同。根据飞碟上的规定，外星人只可以在满足以下条件时从舱段 $a$ 移动到相邻的舱段 $b$：他必须比这两个舱段中所有外星人等级都高（当然，$a$ 和 $b$ 必须相邻）。每个外星人每次移动都需要正好 $1$ 分钟。此外，安全规定要求，每分钟至多只能有一个外星人在飞船上移动。 现阶段，所有宇航员都聚集在第 3 舱段。他们都需要移动到第 1 舱段。队员中有一位编号为 CFR-140 的外星人想计算出，他们完成此任务所需的最少时间（以分钟计）。 请帮助 CFR-140 计算，所有宇航员从第 3 舱段移动到第 1 舱段所需的最少时间（分钟数对 $m$ 取模）。因为答案可能很大，所以只需输出结果对 $m$ 取模的值。

第一行包含两个用空格分隔的整数 $n$ 和 $m$，表示飞碟上的外星人数和需取模的数（$1 \leq n, m \leq 10^9$）。

输出一个整数，即问题的答案对 $m$ 取模的结果。

在第一个样例中，唯一的船员从舱段 3 移到舱段 2，再从舱段 2 移到舱段 1，可以顺利完成。总共需要两分钟。 在第二个样例中，简略地用 $move(i, j)$ 表示等级为 $i$ 的外星人从当前位置移到舱段 $j$。借助这个记法，移动过程如下：                           总共需要 26 次移动。$26\div 8$ 余数为 $2$，因此本例的答案为 $2$。 由 ChatGPT 5 翻译