eolymp
bolt
Try our new interface for solving problems
Məsələlər

Неприводимые многочлены High

Неприводимые многочлены High

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Имеется некоторое простое число 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 (1p, n, m10^9).

Çıxış verilənləri

Выведите в выходной файл количество неприводимых многочленов степени n в поле Z_p по модулю m.

Nümunə

Giriş verilənləri #1
2 2 10
Çıxış verilənləri #1
1