Имеется некоторое простое число \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}.