Discrete Logarithm Bakery

LiM owns a handmade pastry shop which has accumulated P regular customers (where P is a prime number). Whenever a new product is launched, the shop produces a batch of items. Initially, there is 1 sample product. Then, the production process works as follows: in one minute, the shop’s B workers can produce additional items equal to A times the number of items that have been produced so far. Thus, after t minutes the total number of products becomes

\(T = (A+1)^t\),

where \(t \ge 0\) (with \(t=0\) meaning no additional production and only the sample exists).

After production, the P regular customers all buy products: each customer buys the same number of items and they together purchase as many as possible. In doing so, the shop sets aside exactly B items for the workers as a bonus, meaning that after the purchase, exactly B products remain in stock. Therefore, the number of products sold is \(T - B\), and it must be divisible by P.

Your task is to compute the minimum working time (in minutes) \(t\) such that the production total \(T=(A+1)^t\) satisfies
\[ (A+1)^t \equiv B \pmod{P}, \]
so that when the B items are reserved, the remaining items are exactly divisible by P. If no such t exists, output -1.

inputFormat

The input consists of a single line containing three integers A, B, and P separated by spaces. Here, P is a prime number.

For example:

2 3 7

outputFormat

Output a single integer, the minimum number of minutes of production required (i.e. the smallest non-negative integer t satisfying \((A+1)^t \equiv B \pmod{P}\)). If there is no solution, output -1.

sample

2 3 7

1