CF226A.Flying Saucer Segments

An expedition group flew from planet ACM-1 to Earth in order to study the bipedal species (its representatives don't even have antennas on their heads!).

The flying saucer, on which the brave pioneers set off, consists of three sections. These sections are connected by a chain: the 1-st section is adjacent only to the 2-nd one, the 2-nd one — to the 1-st and the 3-rd ones, the 3-rd one — only to the 2-nd one. The transitions are possible only between the adjacent sections.

The spacecraft team consists of n aliens. Each of them is given a rank — an integer from 1 to n. The ranks of all astronauts are distinct. The rules established on the Saucer, state that an alien may move from section a to section b only if it is senior in rank to all aliens who are in the segments a and b (besides, the segments a and b are of course required to be adjacent). Any alien requires exactly 1 minute to make a move. Besides, safety regulations require that no more than one alien moved at the same minute along the ship.

Alien A is senior in rank to alien B, if the number indicating rank A, is more than the corresponding number for B.

At the moment the whole saucer team is in the 3-rd segment. They all need to move to the 1-st segment. One member of the crew, the alien with the identification number CFR-140, decided to calculate the minimum time (in minutes) they will need to perform this task.

Help CFR-140, figure out the minimum time (in minutes) that all the astronauts will need to move from the 3-rd segment to the 1-st one. Since this number can be rather large, count it modulo m.

一支远征队乘坐飞船从行星 ACM-1 飞往地球，以研究一种双足物种（该物种的代表甚至头上都没有天线！）

他们所乘坐的飞碟由三个舱段组成。这三个舱段通过一条链连接：第 1 号舱段仅与第 2 号舱段相邻，第 2 号舱段与第 1 号和第 3 号舱段均相邻，第 3 号舱段仅与第 2 号舱段相邻。人员仅可在相邻舱段之间移动。

飞船乘组共由 $ n $ 名外星人组成。每名外星人都被授予一个等级——一个从 $ 1 $ 到 $ n $ 的整数。所有宇航员的等级互不相同。飞碟上制定的规则规定：一名外星人仅当其等级严格高于当前位于舱段 $ a $ 和舱段 $ b $ 中的所有外星人时，才可从舱段 $ a $ 移动至舱段 $ b $（当然，舱段 $ a $ 与舱段 $ b $ 必须相邻）。任何一名外星人完成一次移动恰好需要 1 分钟。此外，安全规章要求：在任意一分钟内，飞碟上至多只允许一名外星人移动。

外星人 $ A $ 的等级高于外星人 $ B $，当且仅当表示 $ A $ 等级的数值严格大于表示 $ B $ 等级的数值。

目前，整个飞碟乘组全部位于第 3 号舱段。他们全部需要转移到第 1 号舱段。乘组中一名成员——编号为 CFR-140 的外星人——决定计算完成此项任务所需的最短时间（以分钟为单位）。

请帮助 CFR-140 计算所有宇航员从第 3 号舱段转移到第 1 号舱段所需的最少时间（以分钟为单位）。由于该数值可能非常大，请对 $ m $ 取模。

The first line contains two space-separated integers: n and m (1 ≤ n, m ≤ 109) — the number of aliens on the saucer and the number, modulo which you should print the answer, correspondingly.

第一行包含两个以空格分隔的整数：$n$ 和 $m$（$1 ≤ n, m ≤ 10^9$）—— 分别表示飞碟上的外星人数目，以及输出答案时所取模的数。

Print a single number — the answer to the problem modulo m.

输出一个数字——该问题答案对 $m$ 取模的结果。

In the first sample the only crew member moves from segment 3 to segment 2, and then from segment 2 to segment 1 without any problems. Thus, the whole moving will take two minutes.

To briefly describe the movements in the second sample we will use value , which would correspond to an alien with rank i moving from the segment in which it is at the moment, to the segment number j. Using these values, we will describe the movements between the segments in the second sample: , , , , , , , , , , , , , , , , , , , , , , , , , ; In total: the aliens need 26 moves. The remainder after dividing 26 by 8 equals 2, so the answer to this test is 2.

在第一个样例中，唯一的一名船员从第 3 段移动到第 2 段，再从第 2 段移动到第 1 段，全程无任何问题。因此，整个移动过程耗时两分钟。

为简要描述第二个样例中的移动过程，我们引入符号 ，它表示排名为 $i$ 的外星人从其当前所在段移动至编号为 $j$ 的段。利用这些符号，我们可将第二个样例中各段之间的移动描述如下：
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
；
总计：外星人共需 26 次移动。26 除以 8 的余数为 2，因此该测试用例的答案为 2。