Equation 2#1849

Equation 2

4 seconds

256 megabytes

Very easy

Given the equation of the form $X^{N} + Y^{N} \equiv Z^{N} (mod M)$ X^N + Y^N \equiv Z^N \pmod{M}.

For fixed $N$ and $M$ , find the number of different solutions to this equation. A solution is called a triple of positive integers $(X, Y, Z)$ (X, Y, Z), which satisfies:

$1 \leq X \leq Y < M$ 1 \leq X \leq Y < M
$1 \leq Z < M$ 1 \leq Z < M
$X^{N} + Y^{N} \equiv Z^{N} (mod M)$ X^N + Y^N \equiv Z^N \pmod{M}

Input

The input file contains a single line with the numbers $N$ and $M$ ( $1 \leq N, M \leq 50000$ 1 \leq N, M \leq 50000).

Output

Output a single number — the answer to the problem.

Examples

Example 1

Loading

X^{N} + Y^{N} \equiv Z^{N} (mod M)

(X, Y, Z)

1 \leq X \leq Y < M

1 \leq Z < M

X^{N} + Y^{N} \equiv Z^{N} (mod M)

1 \leq N, M \leq 50000