You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

RPK is taking MSH to an even more mysterious place!
RPK leads MSH across the square and presses a button on the 1618th brick, causing a handle to appear on a nearby wall. RPK grasps the handle and opens a stone gate. They walk through a long and fragrant path until they reach a gate symbolizing time—"the gate of time."
Written on the gate is a riddle about time: "Promise: ____ year." After a moment of thought, RPK calmly writes 10,000 with his finger. The gate begins to flash, and MSH feels their heart nearly stop.
The gate opens, revealing a beautiful and mysterious garden!

Just as RPK and MSH are about to enter, an old gatekeeper, QL, suddenly appears.
QL: "What are you doing? You haven't bought tickets yet!"
RPK suddenly remembers they spent all their cash on cakes and asks politely, "Can I pay by card? I don’t have any cash on me."
QL: "No money? Then you can’t enter!"
RPK (sweating): "..."
QL: "Wait, I have an unsolved math problem here. Solve it, and I’ll let you in."
(Everyone: "...")

There is a sequence $\{a_n\}, a_0 = 1, a_{i+1} = (A\times{a_i} + a_i \bmod B) \bmod C$. The task is to find the index of the first occurrence of a repeated term in this sequence.

Of course, such a small problem is no match for the math genius RPK, who calculates the result mentally in no time.

Input Format

One line containing three numbers, representing $A, B, C$.

Output Format

Output the index of the first occurrence of a repeated term. If the answer exceeds $2\times 10^6$, output $-1$.

Sample 1

2 2 9

4

Data Range and Hints

$30\%$ of the data: $A, B, C \le { 10^5 }$;

$100\%$ of the data: $A, B, C \le { 10^9 }$.

For $30\%$ of the data, the original space limit was $4\text{MB}$. (Due to limitations in the evaluation system, this space restriction has been lifted.)