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.




;WITH Iterate(N,A,B,X0,X1)
	AS (
		SELECT 
			1
			,CASE WHEN @a < 0 THEN @b-(-@a % @b) ELSE @a END
			,CASE WHEN @b < 0 THEN -@b ELSE @b END
			,0
			,1
		UNION ALL
		SELECT 
			N+1
			,B
			,A%B
			,X1-((A/B)*X0)
			,X0
		FROM Iterate
		WHERE A != 1 AND B != 0
	),
	ModularInverse(Result)
	AS (
		SELECT
			-1
			FROM Iterate
			WHERE A != 1 AND B = 0
		UNION ALL
		SELECT
			TOP(1)
			CASE WHEN X1 < 0 THEN X1+@b ELSE X1 END AS Result
			FROM Iterate
			WHERE (SELECT COUNT(*) FROM Iterate WHERE A != 1 AND B = 0) = 0
			ORDER BY N DESC
	)
	SELECT *
	FROM ModularInverse