2017 Winter Waterloo Local ACM Contest, Problem E

Vera has $N$ friends numbered from $0$ to $N-1$. Being in Software Engineering, all her friends do not have enough spare time to engage in relationships. However, friends have crushes on each other.

If $x$ is a non-negative integer, let $g(x)$ be the number of ones in the binary representation of $x$.

Let $f(i,j)=g((A\cdot B^{i\cdot N+j})\mathrm{\%}M)$, where $A,B,M$ are integer constants.

It is known that for any 2 friends $i$ and $j$ where $i<j$, if $f(i,j)$ is even then $i$ has a crush on $j$, otherwise $j$ has a crush on $i$.

Vera thinks love triangles are very funny. A love triangle is a set of 3 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 integers $N,M,A,B$ tell Vera how many love triangles exist among her friends. Two love triangles are different if they contain a different set of $3$ friends.

Constraints

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

Input Specification

The input will be in the format:

$N$ $M$ $A$ $B$

Output Specification

Output one line with the number of love triangles.

Sample Input 1

3 5 3 4

Sample Output 1

1

Explanation of Sample Output 1

Let $a\to b$ denote that friend $a$ has a crush on friend $b$.

We have $f(0,1)=1$, $f(0,2)=2$, and $f(1,2)=1$. So $0\to 2$, $2\to 1$, and $1\to 0$, so there is one love triangle.

Sample Input 2

3 3 1 2

Sample Output 2

0

Explanation of Sample Output 2

We have $1\to 0$, $2\to 0$, and $2\to 1$, so there are zero love triangles.

Sample Input 3

1337 10007 1337 1337

Sample Output 3

99141170