Задачі
Рівняння
Рівняння
Задано рівняння виду \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{7^7}).
\OutputFile
У вихідний файл виведіть одне число --- відповідь до задачі.
Вхідні дані #1
1 3
Вихідні дані #1
2