Modular division

Three positive integers $a,b$, and $n$ are given. Compute the value of $a/bmodn$. In other words, find a value $x$ such that $b\cdot x=amodn$.

Input

Three positive integers $a,b,n(n\le 2\cdot 10^9,1\le a,b<n)$. It is known that $n$ is a prime number.

Output

Print the value of $a/bmodn$.

Examples