Имеется некоторое простое число \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}. Поскольку это количество может быть большим, то требуется получить лишь остаток от деления этого числа на \textbf{m}. \InputFile Единственная строка входного файла содержит три числа \textbf{p}, \textbf{n}, \textbf{m} (\textbf{1} ≤ \textbf{p}, \textbf{n}, \textbf{m} ≤ \textbf{10^9}). \OutputFile Выведите в выходной файл количество неприводимых многочленов степени \textbf{n} в поле \textbf{Z_p} по модулю \textbf{m}.