Шахи#7094
Петрик зацікавився шахами. Проте традиційні шахи йому наскучили досить швидко — одразу після того, як він зайняв перше місце з шахів серед юніорів. Тепер він цікавиться варіаціями на тему шахових фігур на різноманітних дошках. Наразі, Петрика цікавить кількість варіантів розташування довільної (можливо, нульової) кількості шахових коней на дошці 4 \times n так, щоб вони не атакували один одного. Проте він не любить працювати з великими числами, і тому Петрику достатньо знайти остачу від ділення цієї кількості на деяке число . Допоможіть йому у цьому нелегкому завданні.
Обчислити остачу від ділення на кількості можливих розміщень шахових коней на дошці 4 \times n, при яких вони не атакують один одного.
В одному рядку записано довжину дошки (2 \le n \le 10^9) та дільник (2 \le p \le 10^9).
Вивести остачу від ділення на кількості можливих розміщень шахових коней на дошці 4 \times n, при яких вони не атакують один одного.
Приклад 1