eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Раскраска

Раскраска

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Имеется 9 квадратных кусочков бумаги одинакового размера. Каждый кусочек может быть покрашен в любой из K цветов. Из этих кусочков склеивают квадрат 3×3. Сколько различных с точностью до поворота квадратов может получиться? Так как ответ может быть довольно большим, выведите остаток от его деления на P.

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

Входной файл содержит два целых числа: K и P (1K1000, 2P2000000000).

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

Выходной файл должен содержать одно целое число - ответ к задаче.

Пример

Входные данные #1
2 200
Выходные данные #1
140
Источник Открытый личный чемпионат ИГЭУ, Иваново, 20.05.2011