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

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

Trong đó:

• \(div\): là phép chia lấy nguyên
• \(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 * 10^7\).

Constants

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

Example

23 12 2001

121