program lgput;
var f,g:text;
n,p,s:integer;
begin
assign(f,'lgput.in');
assign(g,'lgput.out');
reset(f);
rewrite(g);
read(f,n,p);
s:=1;
while p<>0 do
        if p mod 2=0 then begin
                n:=(n*n) mod 1999999973;
                p:=p div 2;
                end
        else begin
                s:=(s*n) mod 1999999973;
                n:=(n*n) mod 1999999973;
                p:=p div 2;
                end;
write(g,s);
close(f);
close(g);
end.