var i,n,p,a,s:int64;

procedure lire;
begin
  assign(input,'lgput.in');
  reset(input);
  read(n,p);
  close(input);
end;

procedure ecrire;
begin
  assign(output,'lgput.out');
  rewrite(output);
  write(s);
  close(output);
end;

begin
  s:=1;
  lire;
  a:=n;
  while ((1 shl i)<=p) do
  begin
    if ( ((1 shl i) and p) > 0) then s:=(s*a) mod 1999999973;
    a:=(a*a) mod 1999999973;
    i:=i+1;
  end;
  ecrire;
end.