모듈러 역원

많은 암호학 응용에서 모듈러 역원(modular inverse)은 핵심적인 개념이다. 이 문제에서는 주어진 수의 모듈러 역원을 구한다.

정수 $x$와 $m$이 $0 < x < m$을 만족한다고 하자. $x$의 모듈러 역원은 $x \times n$을 $m$으로 나눈 나머지가 $1$이 되는 유일한 정수 $n$($0 < n < m$)이다.

예를 들어 $4 \times 13 = 52 = 17 \times 3 + 1$이므로 $52$를 $17$로 나눈 나머지는 $1$이고, 따라서 $13$은 $17$을 법으로 하는 $4$의 역원이다.

입력

첫째 줄에 정수 $x$가, 둘째 줄에 정수 $m$이 주어진다.

출력

$x$의 $m$에 대한 모듈러 역원 $n$을 출력한다. 그러한 정수 $n$이 존재하지 않으면 No such integer exists.를 출력한다.

• $m \le 100$
• $0 < x < m$