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.)