Розфарбовка

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

Вхідні дані

Вхідний файл містить два цілих числа: K та P (1 ≤ K ≤ 1000, 2 ≤ P ≤ 2000000000).

Вихідні дані

Вихідний файл повинен містити одне ціле число - відповідь до задачі.

Приклади