Inversion Count: Crazy Code Monster

The evil gigantic cosmic monster CCM is about to attack Earth! In a desperate moment, the united forces fire the state-of-the-art Super Energy Particle Cannon designed by the famous inventor SHTSC. The cannon consists of n vertical particle tubes (numbered from 1 to n) that simultaneously fire streams of super energy particles. Earth is divided into m regions (numbered from 1 to m) and each tube i targets region f(i) where the function is defined as follows:

$$f(i)= (a\,i+b)\,\bmod\,m + 1$$

In order to stop CCM from being destroyed completely, the nefarious N Corporation decides to tamper with the weapon’s operator — you! You discover that the trajectories of different particle streams cross each other. At each crossing point, a special device called a bounce prism can be deployed to cause the cannon to overload and self-destruct.

Your task is to count the number of pairs of particle streams (i, j) such that i < j and f(i) > f(j). In other words, given the sequence f(1), f(2), ... ,f(n) generated by the above formula, count the number of inversion pairs.

inputFormat

Input is given on a single line containing four space-separated integers: n, m, a, and b. Here, n represents the number of tubes, m the number of regions, and a and b are constants used in the function f(i) defined as $$f(i)= (a,i+b),\bmod,m + 1$$.

outputFormat

Output a single integer representing the number of inversion pairs, i.e. the number of pairs (i, j) with i < j and f(i) > f(j).

sample

5 7 1 0

0