Giải phương trình đồng dư bậc nhất: \(a \times x \equiv b \pmod{M}\). In ra nghiệm không âm nhỏ nhất, hoặc \(-1\) nếu vô nghiệm.

Định dạng đầu vào

• Một dòng chứa ba số nguyên \(a, b, M\) (\(1 \le a, b, M \le 10^9\)).

Định dạng đầu ra

• Một số nguyên là nghiệm \(x \in [0, M-1]\) thỏa phương trình, hoặc \(-1\) nếu vô nghiệm.

Ví dụ

Input:

3 4 7

Output:

6

Giải thích: \(3 \times 6 = 18 \equiv 4 \pmod{7}\).

Ràng buộc

• 100% số điểm: \(M \le 10^9\).