Program invers;
var a : array[0..10000] of longint;
    n,t,x : int64;
    f,g : text;



Function prim(k : int64) : boolean;
var j : longint;
    t : boolean;
begin
j:=2;
t:=true;
while (t) and (j*j<=k) do
begin
if k mod j=0 then t:=false;
inc(j);
end;
prim:=t;
end;


Function tot(k : int64) : int64;
var g,f,s,j,l  : int64;
    i : longint;
begin
if prim(k) then exit(k-1);
g:=k;
l:=0;
for i:=2 to k div 2 do
if prim(i) and (g mod i=0) then
begin
if a[l]<>i then begin inc(l); a[l]:=i; end;
f:=g div i;
g:=f;
if g=1 then break;
end;
s:=k;
j:=1;
for i:=1 to l do
begin
s:=s*(a[i]-1);
j:=j*a[i];
end;
tot:=s div j;
end;


Function exp(a,p : int64) : int64;
var y : int64;
begin
if p=0 then exit(1);
if odd(p) then exp:=((a mod n)*(exp(a,p-1) mod n)) mod n
else begin y:=exp(a,p div 2) mod n; exp:=y*y mod n; end;
end;


begin
assign(f,'inversmodular.in');
reset(f);
readln(f,t,n);
close(f);
x:=exp(t,tot(n)-1);
assign(g,'inversmodular.out');
rewrite(g);
writeln(g,x);
close(g);
end.