Program Inversmodular;
 var f,g:text; a,n:longint;
 function fi (x:longint):longint;
  var i,ft:longint;
  begin
   i:=2; ft:=x;
   while i<=sqrt (x) do begin
     if x mod i=0 then begin
       ft:=(ft div i)*(i-1);
       while x mod i=0 do x:=x div i;
     end;
     inc (i);
   end;
   if x>1 then ft:=(ft div x)*(x-1);
   exit (ft);
  end;
 function putere (x,y:longint):longint;
  var i,j,k:int64;
  begin
   i:=y; j:=1; k:=x;
   while (i>0) do begin
     if odd (i) then j:=(j*k) mod n;
     k:=sqr (k) mod n;
     i:=i div 2;
   end;
   exit (j);
  end;
 begin
  assign (f,'inversmodular.in'); reset (f);
  assign (g,'inversmodular.out'); rewrite (g);
  readln (f,a,n);
  writeln (g,putere (a,fi (n)-1));
  close (f); close (g);
 end.