var a,n:int64;
    f,g:text;

function rid(x,k,n:int64):int64;
var a,b:int64;
begin
if k = 0 then
rid:=1
else

if k mod 2 = 0 then
begin
a:=rid(x,k div 2,n);
rid:=a*a mod n ;
end
else
begin
a:=rid(x,k div 2,n);
b:=a*a mod n;
rid:=b*x mod n;
end;
end;



BEGIN
assign(f,'inversmodular.in');
reset(f);
read(f,a,n);
close(f);


assign(g,'inversmodular.out');
rewrite(g);
writeln(g,rid(a,n-2,n));
close(g);




END.