Competitions

# Exponentiation

# 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** (**n** ≤ **2** * `10`

, ^{9}**1** ≤ **a**, **b** < **n**). It is known that **n** is prime.

#### Output

Print the value of **a** / **b** mod **n**.

Input example #1

3 4 7

Output example #1

6

Input example #2

4 8 13

Output example #2

7