program lgput;
 const r=1999999973;
   var n,p,i,rs:int64;


 begin
 assign(input,'lgput.in'); reset(input);
  readln(n,p);
  assign(output,'lgput.out'); rewrite(output);

  rs:=n;
  repeat
    if p mod 2=1 then begin
        p:=p-1;
        n:=(n*rs)mod r;
        end
        else begin
          p:=p div 2;
          n:=(n*n)mod r;
          end;
    until p=1;
  writeln(n);
  close(output);
 end.