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.




@echo off
setlocal enabledelayedexpansion
	%== Calls the "function" ==%
call :ModInv 42 2017 result
echo !result!
call :ModInv 40 1 result
echo !result!
call :ModInv 52 -217 result
echo !result!
call :ModInv -486 217 result
echo !result!
call :ModInv 40 2018 result
echo !result!
pause>nul
exit /b 0
 
	%== The "function" ==%
:ModInv
	set a=%1
	set b=%2
 
	if !b! lss 0 (set /a b=-b)
	if !a! lss 0 (set /a a=b - ^(-a %% b^))
 
	set t=0&set nt=1&set r=!b!&set /a nr=a%%b
 
	:while_loop
	if !nr! neq 0 (
		set /a q=r/nr
		set /a tmp=nt
		set /a nt=t - ^(q*nt^)
		set /a t=tmp
 
		set /a tmp=nr
		set /a nr=r - ^(q*nr^)
		set /a r=tmp
		goto while_loop
	)
 
	if !r! gtr 1 (set %3=-1&goto :EOF)
	if !t! lss 0 set /a t+=b
	set %3=!t!
	goto :EOF