Задачі
Незвідні многочлени Junior
Незвідні многочлени Junior
Є деяке просте число \textbf{p}. Візьмемо \textbf{Z_p = \{0, 1, ..., p-1\}} -- поле лишків по модулю \textbf{p}. У цьому полі операції множення та додавання виконується по модулю \textbf{p}. Тепер розглянемо нормовані многочлени над цим полем виду
\textbf{f(x)= x^n + a_\{n-1\}x^\{n 1\} + ... + a_1x + a_0},
\includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg}
де \textbf{n} --степінь многочлена, \textbf{x} -- змінна, \textbf{a_i} \textbf{Z_p} --коэефіцієнти.
Так, наприклад, многочлен \textbf{x^2 + x + 1} у полі \textbf{Z_2} незвідний. Нормований многочлен називається незвідним, якщо не можна подати його у вигляді \textbf{f(x)= p(x) · q(x)}, де \textbf{p(x)}, \textbf{q(x)} - многочлени степені меншої, ніж \textbf{f(x)}. І це єдиний незвідний многочлен другої степені і полі \textbf{Z_2}.
Ваша задача -- обчислити кількість незвідних многочленів степені \textbf{n} у полі \textbf{Z_p}.
\InputFile
Єдиний рядок вхідного файлу містить два числа \textbf{p}, \textbf{n} (\textbf{1} ≤ \textbf{p}, \textbf{n} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{p^n} < \textbf{10^18}.).
\OutputFile
Виведіть у вихідний файл кількість незвідних многочленів степені \textbf{n} у полі \textbf{Z_p}.
Вхідні дані #1
2 2
Вихідні дані #1
1