Cho hai số \(a, b, M\) với \(\gcd(a, M) = 1\). Tính \(a / b \pmod{M}\) bằng cách dùng định lý Euler. Biết rằng \(M\) có thể không nguyên tố, nhưng đảm bảo \(\gcd(b, M) = 1\).

Đị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\), \(\gcd(b, M) = 1\)).

Định dạng đầu ra

• Một số nguyên là \(a \times b^{-1} \bmod M\).

Ví dụ

Input:

10 3 10

Output:

0

Giải thích: \(\varphi(10) = 4\), \(3^{-1} \equiv 3^{4-1} = 27 \equiv 7 \pmod{10}\), \(10 \times 7 = 70 \equiv 0 \pmod{10}\).

Ràng buộc

• 100% số điểm: \(M \le 10^9\), \(\gcd(b, M) = 1\).