mod の逆元 (paizaランク C 相当)

ある自然数 M について、整数を M で割った余りに注目した数式を合同式と言います。
整数 A を M で割った余りと、整数 B を M で割った余りが等しい場合、「M を法として A と B は合同である」といい A ≡ B(mod M)と表されます。

M と互いに素である整数 A に対して、 A × N = 1(mod M) となる 1 以上 M 未満の整数 N が必ず存在し、
この N を 「mod M での A の mod 逆元」といい、 A^{-1} (mod M) と書きます。
mod M での A の mod 逆元を求めるには、 x , y についての 1 次方程式 Ax + My = 1 の 解 x が分かれば良いです。
gcd(A,M) = 1 であるので、この方程式の解 x は拡張ユークリッドの互除法を用いることで求めることができます。

互いに素である整数 A , M が与えられるので、mod M での A の mod 逆元を求めてください。
ただし、答えは 1 以上 M 未満の整数で出力してください。