Раскраска

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

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

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

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

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

Примеры