A. Отсеки летающей тарелки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

С планеты 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.

Входные данные

В первой строке записаны два целых числа через пробел: n и m (1 ≤ n, m ≤ 109) — количество инопланетян на тарелке и число, по модулю которого следует вывести ответ, соответственно.

Выходные данные

Выведите единственное число — остаток от деления ответа на задачу на число m.

Примеры
Входные данные
1 10
Выходные данные
2
Входные данные
3 8
Выходные данные
2
Примечание

В первом примере единственный член экипажа без проблем переходит вначале из 3-го отсека во 2-й, а затем из 2-го в 1-й. Таким образом, на все перемещения будет затрачено две минуты.

Для того, чтобы кратко описать перемещения во втором примере введем обозначение , которое будет соответствовать переходу инопланетянина с рангом i из того отсека, в котором он находится в настоящий момент, в отсек с номером j. Пользуясь введенными обозначениями, опишем перемещения между отсеками во втором примере: , , , , , , , , , , , , , , , , , , , , , , , , , ; Итого: требуется 26 перемещений. Остаток от деления 26 на 8 равен 2, поэтому ответ на этот тест 2.