Bộ đếm vòng (Cyclic Counter)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một bộ đếm có $M$ trạng thái được đánh số từ $0$ đến $M-1$. Ban đầu, tại thời điểm $0$, bộ đếm ở trạng thái $0$. Sau mỗi giây, nếu trạng thái hiện tại là $v$ thì trạng thái mới trở thành

Cho $M,A,X$. Hãy tìm thời điểm nguyên không âm nhỏ nhất $T$ mà bộ đếm ở trạng thái $X$. Nếu không bao giờ đạt được trạng thái $X$, in $-1$.

Input

Một dòng chứa ba số nguyên $M,A,X$.

Output

In một số nguyên duy nhất là $T$ theo yêu cầu, hoặc $-1$ nếu không tồn tại.

Subtask

• Subtask 1 (40%): $1\le M\le 10^6$, $1\le A\le 10^18$, $0\le X<M$.
• Subtask 2 (60%): $1\le M,A\le 10^18$, $0\le X<M$.

Ví dụ

Ví dụ 1

Input

12 8 4

Output

2

Giải thích

Dãy trạng thái bắt đầu là $0,8,4,\ldots$, nên thời điểm nhỏ nhất là $T=2$.

Ví dụ 2

Input

10 4 3

Output

-1

Giải thích

Từ trạng thái ban đầu, bộ đếm chỉ đạt các trạng thái chẵn nên không thể đạt trạng thái $3$.