Equation

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