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

Background

Special for beginners, ^_^

Description

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

Format

Input

一行三个数，分别表示 A,B,C（都<=1.2e9）。

Output

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

Samples

2 2 9

4

Limitation

1s, 1024KiB for each test case.