A 工厂的编号机，专门产生数字，用于给工厂的各类设备编号。
大家都知道，既然是用于给设备编号，那么这个编号机产生的数字一定要保证唯一性。
该编号机产生数字的方式如下。如果要产生一个数列 {a_0,a_1 \dots a_n}，则先指定 a_0=1，其余数字的生成方式为：ai+1=(A \times a_i + a_i \mod B) \mod C。
请编程校验一下，该数字机是否有可能产生出重复的数字，如果可能产生重复的数字，请输出第 1 个产生重复数字的编号（请注意，第 1 个产生的数字编号为 0）。
由于工厂的设备不可能超过 2 \times 10^6 台，因此只要产生的前 2 \times 10^6 个数字中无重复，就可以认为不会产生重复的数字，输出 -1。
输入 3 个整数 A,B,C。
按要求输出第 1 个重复数字的编号 或者 -1。
2 2 9
4
对于 30\% 的数据 A,B,C≤10^5。
对于 100\% 的数据 A,B,C≤10^9。