Шахи

Петрик зацікавився шахами. Проте традиційні шахи йому наскучили досить швидко — одразу після того, як він зайняв перше місце з шахів серед юніорів. Тепер він цікавиться варіаціями на тему шахових фігур на різно­манітних дошках. Наразі, Петрика цікавіть кількість варіантів розташування довільної (можливо, нульової) кількості шахових коней на дошці 4×n так, щоб вони не атакували один одного. Проте він не любить працювати з великими числами, і тому Петрику достатньо знайти остачу від ділення цієї кількості на деяке число p. Допоможіть йому у цьому нелегкому завданні.

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

Вхідні дані

В одному рядку записано довжину дошки n (2 ≤ n ≤ 10^9) та дільник p (2 ≤ p ≤ 10^9).

Вихідні дані

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

Приклади