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.




 
REM Modular inverse
E = 42
T = 2017
GOSUB CalcModInv:
PRINT ModInv
END
 
CalcModInv:
REM Increments E Step times until Bal is greater than T 
REM Repeats until Bal = 1 (MOD = 1) and returns Count
REM Bal will not be greater than T + E
D = 0
IF E < T THEN
  Bal = E
  Count = 1
  Loop:
    Step = T - Bal
    Step = Step / E
    Step = Step + 1
    REM So ... Step = (T - Bal) / E + 1
    StepTimesE = Step * E
    Bal = Bal + StepTimesE
    Count = Count + Step
    Bal = Bal - T
    IF Bal <> 1 THEN Loop:
  D = Count
ENDIF
ModInv = D
RETURN
 