Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).
Входные данные
На вход подаются два натуральное числа
a,
p (
\(a,\ p <= 10^{18}
\)).
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 5 |
3 |