var n,p,x:longint;f,g:text;
const a:longint=1999999973;
Begin
assign(f,'lgput.in');reset(f);
assign(g,'lgput.out');rewrite(g);
readln(f,n,p);
x:=n;
while p<>1 do
  If (p mod 2 = 0) and (p<>2) then
      Begin
      x:=(x*x) mod a;
      p:=p div 2;
      end
  else
      Begin
      x:=(x*n) mod a;
      p:=p-1;
      end;
writeln(g,x);
close(f);
close(g);
end.