From Wikipedia:

In modular arithmetic,   the modular multiplicative inverse of an integer    a    modulo    m    is an integer    x    such that





a

x
≡
1


(
mod

m
)

.


{\displaystyle a\,x\equiv 1{\pmod {m}}.}


Or in other words, such that:





∃
k
∈

Z

,

a

x
=
1
+
k

m


{\displaystyle \exists k\in \mathbb {Z} ,\qquad a\,x=1+k\,m}


It can be shown that such an inverse exists   if and only if    a    and    m    are coprime,   but we will ignore this for this task.



Task

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in
your language,   compute the modular inverse of   42 modulo 2017.




100 PRINT MODINV(42,2017)
120 DEF MODINV(A,B)
130   LET B=ABS(B)
140   IF A<0 THEN LET A=B-MOD(-A,B)
150   LET T=0:LET NT=1:LET R=B:LET NR=MOD(A,B)
160   DO WHILE NR<>0
170     LET Q=INT(R/NR)
180     LET TMP=NT:LET NT=T-Q*NT:LET T=TMP
190     LET TMP=NR:LET NR=R-Q*NR:LET R=TMP
200   LOOP
210   IF R>1 THEN
220     LET MODINV=-1
230   ELSE IF T<0 THEN
240     LET MODINV=T+B
250   ELSE
260     LET MODINV=T
270   END IF
280 END DEF