var r,a,t,n:int64;
begin
assign(input,'lgput.in');reset(input);
assign(output,'lgput.out');rewrite(output);
read(a,n);r:=1;
t:=1999999973;
 while n<>0 do begin
  if n mod 2=1 then r:=r*a mod t;
  a:=a*a mod t;
  n:=n div 2;
 end;
writeln(r mod t);
close(input);close(output);
end.