var n,p:int64;
     f,h:text;

Function rest(q:int64):int64;
begin
if q=1 then rest:=(n mod 1999999973) else
             if odd(q) then rest:=((rest(q-1)*n) mod 1999999973)
             else rest:=sqr(rest(q div 2) mod 1999999973);
end;

begin
assign(f,'lgput.in');
reset(f);
read(f,n);
readln(f,p);
assign(h,'lgput.out');
rewrite(h);
writeln(h,rest(p));
close(f);
close(h);
end.