Equation
Very easy
Execution time limit is 6 seconds
Runtime memory usage limit is 256 megabytes
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
Input
In a single line of input file written numbers N and M (1 ≤ N, M ≤ 7^7).
Output
The output file output a single number - the answer to the problem.
Examples
Input #1
Answer #1
Submissions 351
Acceptance rate 12%