Неприводимые многочлены Junior
Имеется некоторое простое число p. Возьмем Z_p = {0, 1, ..., p-1} – поле вычетов по модулю p. В этом поле операции умножения и сложения выполняются по модулю p. Теперь рассмотрим нормированные многочлены над этим полем вида
f(x)= x^n + a_{n-1}x^{n 1} + ... + a_1x + a_0,
где n –степень многочлена, x – переменная, a_i Z_p –коэффициенты.
Так, например, многочлен x^2 + x + 1 в поле Z_2 неприводим. Нормированный многочлен называется неприводимым, если нельзя представить его в виде f(x)= p(x) · q(x), где p(x), q(x) - многочлены степени меньшей, чем f(x). И это единственный неприводимый многочлен второй степени в поле Z_2.
Ваша задача – вычислить количество неприводимых многочленов степени n в поле Z_p.
Входные данные
Единственная строка входного файла содержит два числа p, n (1 ≤ p, n ≤ 10^9, 1 ≤ p^n < 10^18.).
Выходные данные
Выведите в выходной файл количество неприводимых многочленов степени n в поле Z_p.