var f,g:text;
    a,b,c:int64;
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,'lgput.in');
reset(f);
read(f,a,b);
close(f);
c:=1999999973;





assign(g,'lgput.out');
rewrite(g);
writeln(g,rid(a,b,c));
close(g);


END.