# 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%