program puter;
var f:text;
    n,p,a:int64;

function putere(x,n:int64):int64;
begin
  if n=0 then putere:=1
         else if n mod 2=0 then putere:=sqr(putere(x,n div 2) mod 1999999973)mod 1999999973
                           else putere:=(x*(putere(x,n-1)mod 1999999973))mod 1999999973
end;

begin
  assign(f,'lgput.in');
  reset(f);
  readln(f,n,p);
  close(f);
  assign(f,'lgput.out');
  rewrite(f);
  a:=putere(n,p);
  writeln(f,a);
  close(f);
end.