Given the equation of the form X^N + Y^N ≡ Z^N mod M.
Required for fixed N and M, find the number of different solutions to this equation. Solution is called a triple of positive integers (X, Y, Z), which holds:
1 ≤ X ≤ Y < M
1 ≤ Z < M
X^N + Y^N ≡ Z^N mod M
In a single line of input file written numbers N and M (1 ≤ N, M ≤ 7^7).
The output file output a single number - the answer to the problem.