Шахматы

Петя заинтересовался шахматами. Однако традиционные шахматы ему наскучили достаточно быстро - сразу после того, как он занял первое место по шахматам среди юниоров. Теперь он интересуется вариациями на тему шахматных фигур на различных досках. Сейчас Петю интересует количество вариантов расположения произвольного (возможно, нулевого) количества шахматных коней на доске 4 × n так, чтобы они не атаковали друг друга. Однако он не любит работать с большими числами, и поэтому Петя достаточно найти остаток от деления этого количества на некоторое число p. Помогите ему в этом нелегком задании.

Вычислить остаток от деления на p количества возможных размещений шахматных коней на доске 4 × n, при которых они не атакуют друг друга.

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

В одной строке записаны длина доски n (2 ≤ n ≤ 10^9) и делитель p (2 ≤ p ≤ 10^9).

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

Вывести остаток от деления на p количества возможных размещений шахматных коней на доске 4×n, при которых они не атакуют друг друга.

Примеры