const n_max=10001;
const m = 1999999973;
var i,n,p:longint;
    aux,a,sol:int64;
    
    biti:array[0..32] of boolean;
begin
sol:=1;
assign(input,'lgput.in');assign(output,'lgput.out');
reset(input);readln(input,n,p);close(input);
a:=p;i:=32;aux:=65536*65536;
while a>0 do begin
      if a>=aux then begin a:=a-aux; biti[i]:=true;end;
      i:=i-1;aux:=aux div 2;
      end;
a:=n;for i:=0 to 32 do begin
     if biti[i] then sol:=(sol * a) mod m;
     a:=(a * a) mod m;
     end;
rewrite(oiutput);writeln(output,sol);
close(output);
end.