var a,b,c:int64;   
    f:text;   
function alabmodc(a,b,c:int64):int64;   
var aux:int64;   
begin  
c:=1999999973;
if b=1 then alabmodc:=a mod c   
       else if b and 1=1 then alabmodc:=(alabmodc(a,b-1,c)*a) mod c   
                         else begin  
                               aux:=alabmodc(a,b div 2,c);   
                               alabmodc:=(aux*aux) mod c;   
                               end;   
end;   
begin  
assign(f,'modulo.in'); reset(f);   
read(f,a,b,c);   
close(f);   
assign(f,'modulo.out'); rewrite(f);   
writeln(f,alabmodc(a,b,c));   
close(f);   
end.