Here, we consider polynomials in F_{p}[x], that is, polynomials on x whose coefficients are elements of F_{p}={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 F_{p}[x] of a given degree d.
Too difficult? Do not despair! The problem is not so hard, once you know that, in F_{p}[x], every monic polynomial can be written in a unique way as a factor of monic, irreducible polynomials. For instance, in F_{2}[x] there are 4 monic polynomials of degree 2 (in F_{2}[x], all polynomials are monic), but only one of them is irreducible:
x^{2} = x· x x^{2}+1 = (x+1)·(x+1) x^{2}+x = x· (x+1) x^{2}+x+1 = ??? 
In F_{2}[x], there are 8 monic polynomials of degree 3, but only two of them are irreducible:

Input
Input consists of several cases, each with a prime number 2 ≤ p ≤ 30 and an integer number 2 ≤ d ≤ 30. Additionally, we have p^{d} < 10^{9}.
Output
For every case, print the number of monic, irreducible polynomials in F_{p}[x] of degree d.
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