const m=1999999973;
var n,p:longint;
    f,g:text;
function lg(p:longint):longint;
var a:real;
begin
     if p=1 then lg:=n mod m
            else
            begin
               a:=lg(p div 2)mod m;
               if 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,lg(p));
     close(g);
end.