Problems
Modular division
Modular division
Three positive integers a, b and n are given. Find the value of a / b mod n. You must fund such x that b * x = a mod n.
Input data
Three positive integers a, b, n (n ≤ 2 * 10^9, 1 ≤ a, b < n). It is known that n is prime.
Output data
Print the value of a / b mod n.
Examples
Input example #1
3 4 7
Output example #1
6
Input example #2
4 8 13
Output example #2
7