当前没有测试数据。

题目描述

$A$ 工厂的编号机，专门产生数字，用于给工厂的各类设备编号。

大家都知道，既然是用于给设备编号，那么这个编号机产生的数字一定要保证唯一性。

该编号机产生数字的方式如下。如果要产生一个数列 {$a_0,a_1 \dots a_n$}，则先指定 $a_0=1$ ，其余数字的生成方式为： $a$_$i+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$ 。