Bạn được cho một dãy số nguyên như sau :

• \(x_0=1\)
• \(x_{i+1} = (a \times x_i + x_i \text{ div } b) \mod c\)

Trong đó:

• \(\text{div}\): là phép chia lấy nguyên
• \(\text{mod}\): là phép chia lấy dư

Tìm \(n\) nhỏ nhất sao cho tồn tại \(m<n\) và \(x_m=x_n\).

Input

• Ba số nguyên dương \(a,b,c\)

Output

• Số nguyên \(n\). Dữ liệu đảm bảo \(n \leq 2 \cdot 10^7\).

Constants

• \(a \leq 10^4\) và \(1 \leq b,c \leq 10^{14}\)

Example

23 12 2001

121