Məsələlər
Шахматы
Шахматы
\includegraphics{https://static.e-olymp.com/content/52/52206abadb957370fecc0037dd35b7ae16c40aca.jpg}
Петя заинтересовался шахматами. Однако традиционные шахматы ему наскучили достаточно быстро - сразу после того, как он занял первое место по шахматам среди юниоров. Теперь он интересуется вариациями на тему шахматных фигур на различных досках. Сейчас Петю интересует количество вариантов расположения произвольного (возможно, нулевого) количества шахматных коней на доске \textbf{4} × \textbf{n} так, чтобы они не атаковали друг друга. Однако он не любит работать с большими числами, и поэтому Петя достаточно найти остаток от деления этого количества на некоторое число \textbf{p}. Помогите ему в этом нелегком задании.
Вычислить остаток от деления на \textbf{p} количества возможных размещений шахматных коней на доске \textbf{4} × \textbf{n}, при которых они не атакуют друг друга.
\InputFile
В одной строке записаны длина доски \textbf{n }(\textbf{2 }≤ \textbf{n }≤ \textbf{10^9}) и делитель \textbf{p }(\textbf{2 }≤ \textbf{p }≤ \textbf{10^9}).
\OutputFile
Вывести остаток от деления на \textbf{p }количества возможных размещений шахматных коней на доске \textbf{4}×\textbf{n}, при которых они не атакуют друг друга.
Giriş verilənləri #1
2 7
Çıxış verilənləri #1
4
Şərh: Шахматный конь (на рисунке слева обозначен буквой К) атакует до 8 клеток (на этом же рисунке обозначены буквой А).