Bình đang giải một bài toán số học và cần tính \(a / b\) trong modulo. Cho ba số \(a, b, M\) với \(M\) là số nguyên tố và \(b\) không chia hết cho \(M\). Hãy tính \(a \times b^{-1} \bmod 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\), \(M\) nguyên tố).

Định dạng đầu ra

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

Ví dụ

Input:

10 3 7

Output:

1

Giải thích: \(3^{-1} \equiv 5 \pmod{7}\), \(10 \times 5 = 50 \equiv 1 \pmod{7}\).

Ràng buộc

• 100% số điểm: \(1 \le a, b < M \le 10^9\), \(M\) nguyên tố.