Неприводимые многочлены High
Неприводимые многочлены 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_iZ_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.
Giriş verilənləri
Единственная строка входного файла содержит три числа p, n, m (1 ≤ p, n, m ≤ 10^9).
Çıxış verilənləri
Выведите в выходной файл количество неприводимых многочленов степени n в поле Z_p по модулю m.
Nümunə
2 2 10
1