const m=1999999973;
var n,p:real;
    f,g:text;
function lg(p:real):real;
var a:real;
begin
     if p=1 then lg:=trunc(n) mod m
            else
            begin
               a:=trunc(lg(trunc(p) div 2))mod m;
               if trunc(p) mod 2=0 then lg:=trunc(a*a)mod m
                            else lg:=trunc(a*a*n)mod m;
            end;
end;
begin
     assign(f,'lgput.in'); reset(f);
     assign(g,'lgput.out'); rewrite(g);
     readln(f,n,p);
     writeln(g,trunc(lg(p)));
     close(g);
end.