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