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.




function invmod {
  typeset -i a=$1 n=$2
  if (( n < 0 )); then (( n = -n )); fi
  if (( a < 0 )); then (( a = n - (-a) % n )); fi
 
  typeset -i t=0 nt=1 r=n nr q tmp
  (( nr = a % n ))
  while ((  nr )); do
    (( q = r/nr ))
    (( tmp = nt ))
    (( nt = t - q*nt ))
    (( t = tmp ))
    (( tmp = nr ))
    (( nr = r - q*nr ))
    (( r = tmp ))
  done
  if (( r > 1 )); then
    return 1
  fi
  while (( t < 0 )); do (( t += n )); done
  printf '%s\n' "$t"
}
 
invmod 42 2017