Уравнение 2

Дано уравнение вида 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 ≤ 50000).

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

В выходной файл выведите одно число — ответ на задачу.

Примеры