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.




fn mod_inv(a: isize, module: isize) -> isize {
  let mut mn = (module, a);
  let mut xy = (0, 1);
 
  while mn.1 != 0 {
    xy = (xy.1, xy.0 - (mn.0 / mn.1) * xy.1);
    mn = (mn.1, mn.0 % mn.1);
  }
 
  while xy.0 < 0 {
    xy.0 += module;
  }
  xy.0
}
 
fn main() {
  println!("{}", mod_inv(42, 2017))
}