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($a,$n){
        if ([int]$n -lt 0) {$n = -$n}
        if ([int]$a -lt 0) {$a = $n - ((-$a) % $n)}
 
	$t = 0
	$nt = 1
	$r = $n
	$nr = $a % $n
	while ($nr -ne 0) {
		$q = [Math]::truncate($r/$nr)
		$tmp = $nt
		$nt = $t - $q*$nt
		$t = $tmp
		$tmp = $nr
		$nr = $r - $q*$nr
		$r = $tmp
	}
	if ($r -gt 1) {return -1}
	if ($t -lt 0) {$t += $n}
	return $t
}
 
invmod 42 2017