program lgput;
var f,g:text;
    n,p,x,i,j:longint;

begin
assign(f,'lgput.in');
assign(g,'lgput.out');
reset(f);
rewrite(g);
readln(f,n,p);
if p mod 2=0 then begin
  x:=(n mod 1999999973)*(n mod 1999999973);
  i:=2;
  end
else begin
  x:=n mod 1999999973;
  i:=1;
  end;
while i<p do
  if (p-i) mod 2=0 then begin
    x:=(x*x) mod 1999999973;
    i:=2*i;
    end
  else begin
    x:=x*(n mod 1999999973);
    i:=i+1;
    end;
writeln(g,x);
close(f);
close(g);
end.