Out of Sorts

Ann Logan is fascinated with finite sequences of integers. She is particularly interested in sequences of the form $x_1, x_2, \ldots, x_n$ where:

• $x_i = (a x_{i-1} + c) \bmod m$,
• $n, m, a$, and $c$ are positive integer constants,
• $x_0$ is a non-negative integer constant, and
• all $n$ values are distinct.

For example, if $n = 5$, $m = 8$, $a = 1$, $c = 3$, and $x_0 = 3$, the sequence is $6, 1, 4, 7, 2$ ($x_1 = (1 \cdot 3 + 3) \bmod 8 = 6$, $x_2 = (1 \cdot 6 + 3) \bmod 8 = 1$, and so on). She does not count the initial value $x_0$ as part of the sequence.

Ann wants to determine quickly, for any integer value, whether it appears in a finite sequence of this form. Given values of $n, m, a, c$, and $x_0$, she plans to follow this list of steps:

1. Generate the sequence $x_1, \ldots, x_n$ and store it in an array.
2. Sort the array.
3. Perform a binary search of the array for each integer of interest.

Ann's search algorithm is not the most efficient possible, but it is straightforward and understandable to anyone familiar with binary search. At each step, after computing the midpoint with $mid = (low+high)/2$, she first checks whether the value at position $mid$ equals the search value $x$. If not, she narrows the search according to whether $x$ is strictly less than or strictly greater than the value at position $mid$.

Unfortunately, Ann is absent-minded and lost her list of steps. She remembered the first and last step, but she forgot to sort the array before performing the binary search. Naturally, many values present in the unsorted array cannot be found by a binary search, though surprisingly some can. In the example above, both 4 and 7 can be found with Ann's binary search. How many values can be found for various sequences? Don't botch it up!

The input consists of a line containing five integers $n, m, a, c$, and $x_0$ ($1 \le n \le 10^6$, $1 \le m, a, c \le 2^{31} - 1$, $0 \le x_0 \le 2^{31} - 1$). $n$ is the length of the sequence $x_1, \ldots, x_n$ to be generated, and $m, a, c$, and $x_0$ are the constants used to generate the sequence. All values in the generated sequence are guaranteed to be distinct.

Output the number of sequence values that can be found with Ann's binary search, assuming she forgot to sort the sequence.