# Monic irreducible polynomials P64196

Statement

thehtml

Here, we consider polynomials in Fp[x], that is, polynomials on x whose coefficients are elements of Fp={0, 1, 2, …, p−1}, where p is a prime number.

A polynomial is monic if the coefficient of its term with largest degree is 1. A polynomial is irreducible if it cannot be written as the product of two polynomials of smaller degree. Your task is to count the number of monic, irreducible polynomials of Fp[x] of a given degree d.

Too difficult? Do not despair! The problem is not so hard, once you know that, in Fp[x], every monic polynomial can be written in a unique way as a factor of monic, irreducible polynomials. For instance, in F2[x] there are 4 monic polynomials of degree 2 (in F2[x], all polynomials are monic), but only one of them is irreducible:

 x2 = x· x             ⁠ ⁠ x2+1 = (x+1)·(x+1)    ⁠ ⁠ x2+x = x· (x+1)       ⁠ ⁠ x2+x+1 = ⁠ ⁠ ???

In F2[x], there are 8 monic polynomials of degree 3, but only two of them are irreducible:

 x3 = x· x · x                  ⁠ ⁠ ⁠ ⁠ x3 + x2 = x· x· (x+1) x3+1 = (x+1)·(x2+x+1)             ⁠ ⁠ ⁠ ⁠ x3+x2+1 = ⁠ ⁠ ??? x3 + x = x· (x+1)· (x+1)       ⁠ ⁠ ⁠ ⁠ x3 + x2 + x = x· (x2+x+1) x3+x+1 = ⁠ ⁠ ???                  ⁠ ⁠ ⁠ ⁠ x3+x2+x+1 = (x+1)·(x+1)·(x+1)

Input

Input consists of several cases, each with a prime number 2 ≤ p ≤ 30 and an integer number 2 ≤ d ≤ 30. Additionally, we have pd < 109.

Output

For every case, print the number of monic, irreducible polynomials in Fp[x] of degree d.

Public test cases
• Input

```2 2
2 3
2 4
2 30
3 2
3 3
3 4
3 19
29 6
```

Output

```1
2
3
35790267
3
8
18
61171656
99133020
```
• Information
Author
Omer Giménez
Language
English
Official solutions
C++
User solutions
C++