program p4;
var f,g:text;
    a,b,c,aux:longint;
begin
assign(f,'lgput.in');reset(f);
assign(g,'lgput.out');rewrite(g);
readln(f,a,b,c);
aux:=1;
c:=1999999973;
while b>0 do
      begin
      if b mod 2=1 then
      aux:=(aux*a)mod c;
      b:=b div 2;
      a:=(a*a) mod c;
      end;
write(g,aux);
close(f);
close(g);
end.