题目描述

伪随机数生成器（简称 RNG）在统计计算中被广泛使用。最简单且常见的一种是线性同余 RNG，它按照公式 Rn = (aR_{n - 1} + c) mod m 来计算第 (n) 个随机数 (R_n)，其中 (a)、(c) 和 (m) 是常量。例如，当 (a = 15)，(c = 7)，(m = 100) 且起始值 (R_0 = 1) 时，生成的序列为 1, 22, 37, 62, 37, 62, ...

线性 RNG 速度非常快，并且在选择合适的常量时，能够生成令人惊讶的优质随机数序列。有多种衡量 RNG 质量的方法，而你的任务是计算其中一种，即序列中元素之间的最大间隔。更准确地说，给定 (a)、(c)、(m) 和 (R_0) 的值，找出两个元素 (R_i < R_j)，使得：

不存在其他的 (R_k) 满足 (R_i≤ R_k≤ R_j)； 差值 (R_j - R_i) 最大。

输入

输入包含整数 (a)、(c)、(m) 和 (R_0)。

0 ≤ a, c, R0 ≤ 10⁷, 1 ≤ m ≤ 16000000, am + c < 2³²。

输出

输出应包含一个数字，即找到的最大差值。

15 7 100 1

25

来源

2004 年东北欧，远东分区赛