program mire;
var f,g:text;
   a,n,x,y:int64;
procedure inv(var x,y:int64; a,b:int64);
var aux:int64;
begin
 if b=0 then
   begin
     x:=1;
     y:=0;
   end
 else
  begin
    inv(x,y,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);
 readln(f,a,n);
 inv(x,y,a,n);
 if x<=0 then
   x:=x mod n +n;
 writeln(g,x);
close(f);
close(g);
end.