Given three positive integers a, b and n. Find a / b mod n. So you must fund such x that b * x = a mod n.

Input

Three positive integers a, b, n (n ≤ 2 * 109, 1 ≤ a, b < n). It is known that n is prime.

Output

Print the value of a / b mod n.