Незвідні многочлени High
Є деяке просте число 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. Так як ця кількість може бути великою, то потрібно отримати лише залишок від ділення цього числа на m.
Вхідні дані
Єдиний рядок вхідного файлу містить три числа p, n, m (1 ≤ p, n, m ≤ 10^9).
Вихідні дані
Виведіть у вихідний файл кількість незвідних многочленів степені n у полі Z_p.