Lostmonkey's Box Rearrangement

Lostmonkey has finally landed a job as a basic assembly line operator at company fsk. On the assembly line there are \(n\) positions numbered from \(0\) to \(n-1\). Initially, position \(0\) is empty and every other position \(i\) contains a box labeled \(i\). Lostmonkey is required to rearrange the boxes to a predetermined final configuration using the following procedure:

Generating the sequence:
First, five integers \(q, p, m, d, s\) are given (with \(s\) being the final position of the empty slot). Generate a sequence \(c\) by: \[ \begin{aligned} c_0 &= 0,\\ c_{i+1} &= (c_i \times q + p) \bmod m, \quad \text{for } i \ge 0. \end{aligned} \]

Determining final positions for boxes:
For each box, processed in order (i.e. the box originally at position \(i\) for \(i\ge 1\) is considered as the \(i^{th}\) box), its final position is computed by \[ pos_i = (c_i + d \times x_i + y_i) \bmod n, \] where \(x_i\) and \(y_i\) are nonnegative integers chosen to satisfy the following conditions:

• For each box, the computed \(pos_i\) must not equal \(s\) (the designated empty position) and must be different from all previously assigned final positions.
• If there exist several pairs \((x_i, y_i)\) that can achieve a valid \(pos_i\), you must choose the pair so that the overall sequence \(y = (y_0,y_1,\ldots)\) is lexicographically minimum. If there is a tie, choose the one that makes \(x = (x_0,x_1,\ldots)\) lexicographically minimum.

This produces a final configuration in which every box occupies its computed final position and the empty slot is at \(s\).

Rearranging the boxes:
Initially, boxes are placed as follows: position \(0\) is empty and for \(1 \le i \le n-1\), box \(i\) is at position \(i\). In one move, you may move any box into the empty slot; the slot it leaves behind then becomes empty. Determine the minimum number of moves required to achieve the final configuration.

Note on Moves:
This is equivalent to reordering a permutation via swaps with an empty slot. If we define a mapping \(f\) on positions where for position \(i\) the box initially there should end up at position \(f(i)\) (with \(f(0)=s\) for the empty and for \(i\ge 1,\ f(i)=\) the computed final position of box \(i\)), then the minimal number of moves required to achieve the permutation is given by summing up over each cycle in the permutation:

• If a cycle contains the empty slot (i.e. index 0), the number of moves required is \(L-1\), where \(L\) is the length of the cycle.
• If a cycle does not contain the empty slot and \(L \ge 2\), then it takes \(L+1\) moves to resolve the cycle. (Cycles of length 1 that do not require any move can be ignored.)

Your task is to compute and output the minimum number of moves required.

inputFormat

The input consists of a single line containing six integers:

\(n\) \(q\) \(p\) \(m\) \(d\) \(s\)

where \(n\) is the number of positions on the assembly line, and the other parameters are as described in the problem.

outputFormat

Output a single integer — the minimum number of moves required to rearrange the boxes into their final configuration.

sample

3 2 1 5 1 2

2

</p>