e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Euler Function

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

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

Output

Print the value of a / b mod n.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 4 7
Output example #1
6
Input example #2
4 8 13
Output example #2
7
Author Michael Medvedev