program dsd;
var f,g:text;
n,p,nr,i:longint;
solutie,a:qword;
c:array[1..10000] of 0..1;
begin
assign(f,'lgput.in'); reset(f);
assign(g,'lgput.out'); rewrite(g);
readln(f,n,p); a:=n;
   while p<>0 do
     begin
       nr:=nr+1;
       c[nr]:=p mod 2;
       p:=p div 2;
     end;
     solutie:=1;
     for i:=1 to nr do
       begin
         if c[i]=1 then
           solutie:=(solutie*a) mod 1999999973;
           a:=(a*a) mod 1999999973;
       end;
     write(g,solutie);
close(f);
close(g);
end.