The evil giant space monster CCM (Crazy Code Monster) is about to launch an attack on the beautiful Earth! At this critical moment, the Earth United Army decides to use the most advanced energy weapon—the super particle cannon designed by the inventor SHTSC—to completely destroy CCM.

The super particle cannon consists of $n$ super particle emission tubes arranged vertically from top to bottom, numbered $1$ to $n$. All emission tubes will fire powerful super particle streams simultaneously at the moment of ignition. To completely destroy the evil space monster CCM, which has strong regenerative capabilities, the Earth United Army has divided CCM into $m$ regions from top to bottom, numbered $1$ to $m$, to be targeted separately. The $i$-th emission tube of the super particle cannon will target region $f(i)$. The formula for $f(i)$ is as follows:

$$f(i) = (a \cdot i + b) \pmod m + 1$$

where $a$ and $b$ are given constants.

However, for some ulterior motive, the N Consortium does not want CCM to be completely destroyed by the super particle cannon. Therefore, the N Consortium has remotely mind-controlled the operator of the super particle cannon—you—to prevent the Earth Army from destroying CCM.

You discover that the firing pattern of the super particle cannon causes the trajectories of different particle streams to intersect, and deploying an energy reflection device called a "warp prism" at all these intersection points would cause the super particle cannon to overload and self-destruct. In this way, you can prevent the Earth United Army from using the super particle cannon to destroy CCM and become the winner of the next generation of the N Consortium's gold medal.

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

Input

The first line contains four integers: $n, m, a, b$. These represent the number of emission tubes of the super particle cannon, the number of regions CCM is divided into, and the constants in the formula for $f$ described in the problem, respectively.

Output

Output a single integer representing the number of pairs of particle streams whose trajectories intersect.

Examples

Input 1

2 3 2 2

Output 1

1

Input 2

5 5 2 0

Output 2

7

Constraints

• For $10\%$ of the data, $n \le 5000$.
• For $20\%$ of the data, $n \le m \le 10^6$.
• For an additional $20\%$ of the data, $b = 0$.
• For $80\%$ of the data, $1 \le a \le 1000$.
• For $100\%$ of the data, $n \le m \le 10^9$, there exists $a'$ such that $a \cdot a' \equiv 1 \pmod m$, and $\min\{a, a'\} \le 1000$, $a, b < m$, and $m$ is a prime number.