An đang nghiên cứu về mật mã khóa công khai. Cô ấy có phương trình \(a^x \equiv b \pmod{p}\) với \(p\) nguyên tố lớn. Tuy nhiên \(p-1\) chỉ gồm các thừa số nguyên tố nhỏ. Hãy giúp An tìm \(x\) bằng thuật toán Pohlig-Hellman.

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

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

Định dạng đầu ra

• Một số nguyên \(x\) hoặc \(-1\) nếu không có nghiệm.

Ví dụ

Input:

2 3 7

Output:

5

Ràng buộc

• 100% số điểm: \(p \le 10^9\), \(p-1\) là tích các số nguyên tố nhỏ.