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.




INT FUNC ModInverse(INT a,b)
  INT t,nt,r,nr,q,tmp
 
  IF b<0 THEN b=-b FI
  IF a<0 THEN a=b-(-a MOD b) FI
  t=0 nt=1
  r=b nr=a MOD b
  WHILE nr#0
  DO
    q=r/nr
    tmp=nt nt=t-q*nt t=tmp
    tmp=nr nr=r-q*nr r=tmp
  OD
  IF r>1 THEN
    RETURN (-1)
  FI
  IF t<0 THEN
    t==+b
  FI
RETURN (t)
 
PROC Test(INT a,b)
  INT res
 
  res=ModInverse(a,b)
  IF res>=0 THEN
    PrintF("%I MODINV %I=%I%E",a,b,res)
  ELSE
    PrintF("%I MODINV %I has no result%E",a,b)
  FI
RETURN
 
PROC Main()
  Test(42,2017)
  Test(40,1)
  Test(52,-217)
  Test(-486,217)
  Test(40,2018)
RETURN