program lgput;
var f,g:text;
    n,p:qword;
    i,nr:integer;
    a:longint;
    v:array[1..10000] of 0..1;

begin
 assign (f,'lgput.in'); reset(f);
 assign (g,'lgput.out'); rewrite (g);
 read (f,n,p);
 nr:=0;
 while p<>0 do
 begin
  inc(nr);
  v[nr]:=p mod 2;
  p:=p div 2;
 end;
 a:=n;
 p:=1;
 for i:=1 to nr do
 begin
  if v[i]=1 then
   p:=(p*a) mod 1999999973;
   a:=(a*a) mod 1999999973;
 end;
 write (g,p);
 close (f); close (g);
end.