Задачи
Уравнение 2
Уравнение 2
Дано уравнение вида \textbf{X^N} + \textbf{Y^N} ≡ \textbf{Z^N mod M}.
Требуется для фиксированных \textbf{N} и \textbf{M} найти количество различных решений этого уравнения. Решением назовём такую тройку натуральных чисел (\textbf{X}, \textbf{Y}, \textbf{Z}), что выполняется:
\begin{itemize}
\item \textbf{1} ≤ \textbf{X} ≤ \textbf{Y} < \textbf{M}
\item \textbf{1 }≤ \textbf{Z} < \textbf{M}
\item \textbf{X^N} + \textbf{Y^N} ≡ \textbf{Z^N mod M}
\end{itemize}
\InputFile
В единственной строке входного файла записаны числа \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{50000}).
\OutputFile
В выходной файл выведите одно число --- ответ на задачу.
Входные данные #1
1 3
Выходные данные #1
2