program ridicare;
var f,g:text;
    n,p,solutie:qword;
    i,nr:longint;
    a:qword;
    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;    a:=n;
 while p<>0 do
 begin
  nr:=nr+1; v[nr]:=p mod 2; p:=p div 2;
 end;
 solutie:=1;
 for i:=1 to nr do
 begin
 if v[i]=1 then
  solutie:=(solutie*a) mod 1999999973;
  a:=(a*a) mod 1999999973;
 end;
 write (g,solutie);
 close (f); close (g);
end.