program ddd;
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);      nr:=0; 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.