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ố.