29682번 - Обратные числа 다국어

문제

Позавчера Рома узнал про новую для него операцию в математике --- взятие по модулю, которая обозначается $a \operatorname{mod} m,ドル например 5ドル \operatorname{mod} 3 = 2$. Напомним, что $a \operatorname{mod} m = b,ドル если $a = m \cdot k + b$ и 0ドル \le b < m$ (все перечисленные числа целые).

Вчера Рома начал перемножать числа, и заметил, что бывают такие случаи, что $(a \cdot b) \operatorname{mod} m = 1$ (причем не обязательно оба числа равны единице). И это его очень заинтересовало, он даже придумал название этому феномену --- числа $a$ и $b$ взаимно обратны по модулю $m$.

Сегодня утром Рома начал рассматривать простые числа $m$. Он доказал, что в таком случае для любого числа $a: 1 \le a < m$ существует ровно одно $b,ドル такое что $(a \cdot b) \operatorname{mod} m=1$. Однако он не знает, как по числам $a$ и $m$ найти число $b$. Помогите ему!

입력

В единственной строчке входного файла заданы числа $a$ и $m$ (1ドル \le a<m \le 2 \cdot 10^9$). Число $m$ --- простое.

출력

В выходной файл выведите число $b,ドル такое что $(a\cdot b) \operatorname{mod} m=1$. Оно должно также удовлетворять неравенству 1ドル \le b < m$.

제한

힌트