Vera and Love Triangles

Vera has $N$ friends numbered $0$ through $N-1$. They all study software engineering, so none of them has spare time for a relationship, but they still have crushes on each other.

For a non-negative integer $x$, let $g(x)$ be the number of ones in the binary representation of $x$. With integer constants $A$, $B$, $M$, define $f(i, j) = g((A \cdot B^{i \cdot N + j}) \bmod M)$.

For friends $i$ and $j$ with $i < j$, friend $i$ has a crush on friend $j$ when $f(i, j)$ is even, and friend $j$ has a crush on friend $i$ when $f(i, j)$ is odd.

Vera finds love triangles funny. A love triangle is a set of three friends $i$, $j$, $k$ such that $i$ has a crush on $j$, $j$ has a crush on $k$, and $k$ has a crush on $i$.

Given $N$, $M$, $A$, $B$, count the love triangles among Vera's friends. Two love triangles are different when their sets of three friends differ.

The first line contains $N$, $M$, $A$, $B$ separated by spaces.

Constraints:

• $3 \le N \le 200000$, $3 \le M \le 200000$
• $0 < A < M$, $0 < B < M$
• $N$, $M$, $A$, $B$ are integers.
• $M$ is prime.

Print the number of love triangles on one line.

Write $a \to b$ when friend $a$ has a crush on friend $b$.

In the first sample, $f(0, 1) = g(2) = 1$, $f(0, 2) = g(3) = 2$, and $f(1, 2) = g(2) = 1$. So $0 \to 2$, $2 \to 1$, $1 \to 0$, and there is one love triangle.

In the second sample, $1 \to 0$, $2 \to 0$, and $2 \to 1$, so there is no love triangle.