该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】（想要快，想要省空间需自建hash）

有一个数列满足：$a_0=1$ , $a_{i+1}=(A \times a_i + a_i \bmod B) \bmod C$ ，求这个数列第一次出现重复项的下标。

【输入格式】

一行三个数 $A,B,C(|A|,|B|,|C| \le 10^9)$。

【输出格式】

输出第一次出现重复项的位置，如果答案超过 $2 \times 10^6$ 输出 -1。

【输入样例】

2 2 9

【输出样例】

4