const n_max=10001;
const m = 1999999973;
var i,n,p:longint;
    aux,a,sol:int64;
    f,f2:text;
    biti:array[0..32] of boolean;
begin
sol:=1;
assign(f,'lgput.in');
assign(f2,'lgput.out');
reset(f);
readln(f,n,p);
close(f);
a:=p;
i:=32;
aux:=256*256*256*256;
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
   begin
    sol:=(sol * a) mod m;
   end;
  a:=(a * a) mod m;
 end;
rewrite(f2);
writeln(f2,sol);
close(f2);
end.