CF172B.Pseudorandom Sequence Period

Polycarpus has recently got interested in sequences of pseudorandom numbers. He learned that many programming languages generate such sequences in a similar way: (for i ≥ 1). Here a, b, m are constants, fixed for the given realization of the pseudorandom numbers generator, _r_0 is the so-called randseed (this value can be set from the program using functions like RandSeed(r) or srand(n)), and denotes the operation of taking the remainder of division.

For example, if a = 2, b = 6, m = 12, _r_0 = 11, the generated sequence will be: 4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ....

Polycarpus realized that any such sequence will sooner or later form a cycle, but the cycle may occur not in the beginning, so there exist a preperiod and a period. The example above shows a preperiod equal to 1 and a period equal to 2.

Your task is to find the period of a sequence defined by the given values of a, b, m and _r_0. Formally, you have to find such minimum positive integer t, for which exists such positive integer k, that for any i ≥ k: r__i = r__i + t.

波利卡普斯最近对伪随机数序列产生了兴趣。他了解到，许多编程语言都以类似的方式生成此类序列：
（其中 $i \geq 1$）。
此处 $a$、$b$、$m$ 是常数，对给定的伪随机数生成器实现是固定的；$r_0$ 称为 randseed（该值可通过类似 RandSeed(r) 或 srand(n) 的函数在程序中设置）；而
表示取模运算（即除法的余数）。

例如，若 $a = 2$，$b = 6$，$m = 12$，$r_0 = 11$，则生成的序列为：
$4,\ 2,\ 10,\ 2,\ 10,\ 2,\ 10,\ 2,\ 10,\ 2,\ 10,\ \ldots$

波利卡普斯意识到，任何这样的序列迟早都会形成一个循环，但该循环未必从序列起始处开始，因此存在一个前周期（preperiod）和一个周期（period）。上述例子中前周期长度为 $1$，周期长度为 $2$。

你的任务是：对于给定的 $a$、$b$、$m$ 和 $r_0$ 所定义的序列，求出其周期。
形式化地说，你需要找出最小的正整数 $t$，使得存在某个正整数 $k$，满足对任意 $i \geq k$，均有 $r_i = r_{i+t}$。

The single line of the input contains four integers a, b, m and _r_0 (1 ≤ m ≤ 105, 0 ≤ a, b ≤ 1000, 0 ≤ _r_0 < m), separated by single spaces.

输入仅包含一行，其中有四个整数 $a$、$b$、$m$ 和 $r_0$（$1 \leq m \leq 10^5$，$0 \leq a, b \leq 1000$，$0 \leq r_0 < m$），以单个空格分隔。

Print a single integer — the period of the sequence.

输出一个整数——该序列的周期。

The first sample is described above.

In the second sample the sequence is (starting from the first element): 0, 3, 4, 1, 0, 3, 4, 1, 0, ...

In the third sample the sequence is (starting from the first element): 33, 24, 78, 78, 78, 78, ...

第一个样例如上所述。

第二个样例中，该序列（从第一个元素开始）为：0, 3, 4, 1, 0, 3, 4, 1, 0, ...

第三个样例中，该序列（从第一个元素开始）为：33, 24, 78, 78, 78, 78, ...