Деление по модулю

Задані три натуральних числа $a,b$ і $n$. Обчисліть $a/bmodn$. Тобто знайдіть таке значення $x$, для якого $b\cdot x=amodn$.

Вхідні дані

Три натуральних числа $a,b,n(n\le 2\cdot 10^9,1\le a,b<n)$. Відомо, що $n$ — просте.

Вихідні дані

Виведіть значення $a/bmodn$.

Приклади