program invers_modular;
var f,g:Text;
    n,a:longint;
    x,y:int64;

procedure euler (a,b:longint);
var aux:longint;
begin
 if b=0 then
 begin
  x:=1; y:=0;
 end
 else
 begin
  euler (b,a mod b);
  aux:=x;
  x:=y; y:=aux-(a div b)*y;
 end;
end;

begin
 assign (f,'inversmodular.in'); reset (f);
 assign (g,'inversmodular.out'); rewrite (g);
 read (f,a,n);
 euler (a,n);
 while x<0 do
  x:=n+x mod n;
 write (g,x);
 close (f); close (g);
end.