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.




procedure main(args)
    a := integer(args[1]) | 42
    b := integer(args[2]) | 2017
    write(mul_inv(a,b))
end
 
procedure mul_inv(a,b)
    if b == 1 then return 1
    (b0 := b, x0 := 0, x1 := 1)
    while a > 1 do {
        q := a/b
        (t := b, b := a%b, a := t)
        (t := x0, x0 := x1-q*x0, x1 := t)
        }
    return if (x1 > 0) then x1 else x1+b0
end