Имеется 9 квадратных кусочков бумаги одинакового размера. Каждый кусочек может быть покрашен в любой из K цветов. Из этих кусочков склеивают квадрат 3×3. Сколько различных с точностью до поворота квадратов может получиться? Так как ответ может быть довольно большим, выведите остаток от его деления на P.
Входной файл содержит два целых числа: K и P (1 ≤ K ≤ 1000, 2 ≤ P ≤ 2000000000).
Выходной файл должен содержать одно целое число - ответ к задаче.