10096_RandomGap

The pseudo-random number genegators (or RNGs for short) are widely used in statistical calculations. One of the simplest and ubiquitious is the linear congruence RNG, that calculates the n-th random number R_n as R_n = (a*R_n-1 + c) mod m, where a, c and m are constants. For example, the sequence for a = 15, c = 7, m = 100 and starting value R₀ = 1 is 1, 22, 37, 62, 37, 62, ...

Linear RNG is very fast, and can yield surprisinly good sequence of random numbers, given the right choice of constants. There are various measures of RNG quality, and your task is to calculate one of them, namely the longest gap between members of the sequence. More precisely, given the values of a, c, m, and R₀, find such two elements R_i < R_j that:

1. there are no other Rk that R_i ≤ R_k ≤ R_j,

2. the difference R_j - R_i is maximal.

Input contains integer numbers a  c  m  R₀.

0 ≤ a, c, R₀ ≤ 10⁷, 1 ≤ m ≤ 16000000, a*m + c < 2³².

Output should contain the single number --- the maximal difference found.

15 7 100 1

25