Problem Background

SHOI2014 Day1 T3

Problem Description

The evil giant cosmic monster CCM (Crazy Code Monster) is about to launch an attack on the beautiful Earth!

In this critical moment, the Earth Union Army decides to use the most advanced energy weapon on Earth—the Super Particle Cannon designed by inventor SHTSC—to completely destroy CCM.

The Super Particle Cannon consists of $n$ super particle发射管s arranged vertically from top to bottom, numbered $1 \sim n$. All发射管s will simultaneously emit powerful super particle streams at the moment of firing.

To completely destroy the highly regenerative evil cosmic monster CCM, the Earth Union Army divides CCM into $m$ regions, numbered $1 \sim m$, for targeted strikes. The $i$-th发射管 of the Super Particle Cannon will aim at region $f(i)$, where $f(i)$ is given by the formula:
$$f(i) = (ai + b) \bmod m + 1$$
where $a$ and $b$ are given constants.

However, for some undisclosed purpose, the N Consortium does not want CCM to be completely annihilated by the Super Particle Cannon. Therefore, the N Consortium remotely controls the operator of the Super Particle Cannon—you—to prevent the Earth Army from destroying CCM.

You find that the firing mode of the Super Particle Cannon causes the trajectories of different particle streams to intersect, and deploying a type of energy reflection device called a Warp Prism at all these intersection points will cause the Super Particle Cannon to overload and self-destruct. This way, you can prevent the Earth Union Army from using the Super Particle Cannon to destroy CCM and become the next N Consortium gold medal winner.

To implement this plan, you need to know how many pairs of particle streams $(i, j)$ exist such that $i < j$ and $f(i) > f(j)$.

Input Format

The first line contains four integers $n, m, a, b$. These represent the number of发射管s in the Super Particle Cannon, the number of regions CCM is divided into, and the constants in the formula for $f$ as described in the problem.

Output Format

Output a single integer, which is the number of pairs of particle streams whose trajectories intersect.

Sample Input and Output

Sample Input #1

2 3 2 2

Sample Output #1

1

Sample Input #2

5 5 2 0

Sample Output #2

7

Notes

For 10% of the data, $n \leq 5 \times 10^3$.

For 20% of the data, $n \leq m \leq 10^6$.

For an additional 20% of the data, $b = 0$.

For 80% of the data, $1 \leq a \leq 1000$.

For 100% of the data, $n \leq m \leq 10^9$, there exists $a'$ such that $a \times a' = 1 \pmod m$, and $\min \{a, a'\} \leq 1000, a, b < m$, where $m$ is a prime number.

见题面 Input 部分

见题面 Output 部分