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.




EnableExplicit
Declare main()
Declare.i mi(a.i, b.i)
 
If OpenConsole("MODULAR-INVERSE")
  main() : Input() : End
EndIf
 
Macro ModularInverse(a, b)  
  PrintN(~"\tMODULAR-INVERSE(" + RSet(Str(a),5) + "," + 
         RSet(Str(b),5)+") = " + 
         RSet(Str(mi(a, b)),5))   
EndMacro
 
Procedure main()
  ModularInverse(42, 2017)  ; = 1969
  ModularInverse(40, 1)     ; = 0
  ModularInverse(52, -217)  ; = 96
  ModularInverse(-486, 217) ; = 121
  ModularInverse(40, 2018)  ; = -1
EndProcedure
 
Procedure.i mi(a.i, b.i)
  Define x.i = 1,
         y.i = Int(Abs(b)),
         r.i = 0  
  If y = 1 : ProcedureReturn 0 : EndIf  
  While x < y
    r = (a * x) % b   
    If r = 1 Or (y + r) = 1
      Break
    EndIf
    x + 1
  Wend
  If x > y - 1 : x = -1 : EndIf  
  ProcedureReturn x  
EndProcedure