Irreducible Polynomials High

Given a prime number (p), consider the set (Z_p = {0, 1, ..., p-1}), which represents the field of residues modulo (p). In this field, both multiplication and addition are performed modulo (p). We are interested in monic polynomials over this field, which take the form:

[ f(x) = x^n + a_n-1x^n-1 + ...+ a_1x + a_0 ]

where (n) is the degree of the polynomial, (x) is the variable, and the coefficients (a_i) belong to (Z_p).

For instance, the polynomial (x^2 + x + 1) is irreducible in the field (Z_2). A monic polynomial is deemed irreducible if it cannot be factored into (f(x) = p(x) $\cdot$ q(x)), where (p(x)) and (q(x)) are polynomials of lower degree than (f(x)). Notably, (x^2 + x + 1) is the sole irreducible polynomial of degree two in (Z_2).

Your task is to determine the number of irreducible polynomials of degree (n) in the field (Z_p). Given that this number can be quite large, you are required to compute only the remainder when this number is divided by (m).

Input

The input consists of a single line containing three integers: (p), (n), and (m) ((1 $\le$ p, n, m $\le$ 10^9)).

Output

Output the remainder of the number of irreducible polynomials of degree (n) in the field (Z_p) when divided by (m).

Examples