Рівняння

Задано рівняння виду X^N + Y^N ≡ Z^N mod M.

Потрібно для фіксованих N і M знайти кількість різних розв'язків цього рівняння. Розв'язком назвемо таку трійку натуральних чисел (X, Y, Z), що виконується:

• 1 ≤ X ≤ Y < M

• 1 ≤ Z < M

• X^N + Y^N ≡ Z^N mod M

Вхідні дані

У єдиному рядку вхідного файлу записано числа N і M (1 ≤ N, M ≤ 7^7).

Вихідні дані

У вихідний файл виведіть одне число — відповідь до задачі.

Приклади