Description

有一数组a[n],a[0]=1,a[i+1]=(A*a[i]+a[i]%B)%C,如果你发现当前数组值出现过，你需要输出当前数组的下标，如果下标超过2e6，输出“-1”

Format

Input

一行，三个整数表示A,B,C（0< A,B,C<=1e9）

Output

输出一行，表示答案

Samples

2 2 9

4

Hint