Irreducible Polynomials Junior

Given a prime number (p), consider the set (Z_p = {0, 1, ..., p-1}), which represents the field of remainders modulo (p). In this field, both multiplication and addition are performed modulo (p). Now, let's examine monic polynomials over this field, expressed in 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) in the field (Z_2) is irreducible. A monic polynomial is deemed irreducible if it cannot be factored into (f(x) = p(x) $\cdot$ q(x)), where both (p(x)) and (q(x)) are polynomials of lower degree than (f(x)). Notably, this is the sole irreducible polynomial of degree two in the field (Z_2).

Your task is to determine the number of irreducible polynomials of degree (n) in the field (Z_p).

Input

The input consists of a single line containing two integers (p) and (n) ((1 $\le$ p, n $\le$ 10^9), (1 $\le$ p^n < 10^18)).

Output

Output the number of irreducible polynomials of degree (n) in the field (Z_p).

Examples