모듈러 역원

로마는 그저께 새로운 수학 연산인 모듈러 연산을 배웠다. $a \operatorname{mod} m$로 표기하며, 예를 들어 $5 \operatorname{mod} 3 = 2$이다. $a \operatorname{mod} m = b$는 $a = m \cdot k + b$이고 $0 \le b < m$을 만족한다는 뜻이다(모든 수는 정수이다).

어제 로마는 수를 곱해 보다가 두 수가 모두 1이 아니어도 $(a \cdot b) \operatorname{mod} m = 1$이 되는 경우가 있다는 것을 발견했다. 그는 이 현상에 흥미를 느껴 $a$와 $b$를 모듈러 $m$에 대해 서로 역이 되는 수라고 이름 붙였다.

오늘 아침 로마는 소수 $m$을 살펴보았다. 그는 $1 \le a < m$인 모든 $a$에 대해 $(a \cdot b) \operatorname{mod} m = 1$을 만족하는 $b$가 정확히 하나 있음을 증명했다. 하지만 $a$와 $m$으로부터 $b$를 구하는 방법은 알지 못한다. 로마를 도와주자.

첫 줄에 수 $a$와 $m$이 주어진다 ($1 \le a < m \le 2 \cdot 10^9$). 수 $m$은 소수이다.

$(a \cdot b) \operatorname{mod} m = 1$을 만족하는 $b$를 출력한다. $b$는 $1 \le b < m$을 만족해야 한다.