You are given a sequence of signed 64-bit integers defined as follows:
Let's call a sequence element xp _repeatable_ if it occurs later in the sequence — meaning that there exists such q, q > p, that xq = xp. The _first repeatable_ element M of the sequence is such an element xm that xm is _repeatable_, and none of the xp where p < m are _repeatable_.
Given A, B and C, your task is to find the index of the second occurrence of the _first repeatable_ element M in the sequence if the index is less or equal to 2·107. Per definition, the first element of the sequence has index 0.
The only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0).
Print a single integer — the index of the second occurence of the _first repeatable_ member if it is less or equal to 2·107. Print - 1 if the index is more than 2·107.
In the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The _first repeatable_ element is 3. The second occurence of 3 has index 4.
In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The _first repeatable_ element is 0. The second occurence of 0 has index 5.
In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The _first repeatable_ element is 1. The second occurence of 1 has index 4.
## Input
The only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0).
## Output
Print a single integer — the index of the second occurence of the _first repeatable_ member if it is less or equal to 2·107. Print - 1 if the index is more than 2·107.
[samples]
## Note
In the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The _first repeatable_ element is 3. The second occurence of 3 has index 4. In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The _first repeatable_ element is 0. The second occurence of 0 has index 5. In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The _first repeatable_ element is 1. The second occurence of 1 has index 4.
**Definitions**
Let $ A, B, C \in \mathbb{Z} $ with $ B > 0 $, $ C > 0 $.
Define the sequence $ (x_i)_{i=0}^{\infty} $ by:
$$
x_0 = A, \quad x_{i} = (x_{i-1} \cdot B + C) \mod 2^{64} \quad \text{for } i \geq 1.
$$
An element $ x_p $ is *repeatable* if $ \exists q > p $ such that $ x_q = x_p $.
The *first repeatable* element $ M $ is $ x_m $, where $ m $ is the smallest index such that $ x_m $ is repeatable.
Let $ j $ be the index of the *second occurrence* of $ M $, i.e., the smallest $ j > m $ such that $ x_j = x_m $.
**Constraints**
- $ B > 0 $, $ C > 0 $
- All values are signed 64-bit integers (modulo $ 2^{64} $ arithmetic)
- We only consider $ j \leq 2 \cdot 10^7 $
**Objective**
Compute $ j $ if $ j \leq 2 \cdot 10^7 $; otherwise output $ -1 $.