type vec=array[1..2000000] of 0..1;
var v:vec;
    i,a,b,c,s,k:longint;
begin
assign(input,'lgput.in');reset(input);
assign(output,'lgput.out');rewrite(output);

read(a,b);
c:=1999999973;

k:=1;
while b>1 do
        begin
        if b mod 2=0 then
                        begin
                        v[k]:=0;
                        inc(k);
                        b:=b div 2;
                        end
                     else
                        begin
                        v[k]:=1;
                        inc(k);
                        b:=b-1;
                        end;
        end;

s:=a;
for i:=(k-1) downto 1 do
        if v[i]=0 then
                        s:=((s mod c)*(s mod c)) mod c
                  else
                        s:=((s mod c)*(a mod c)) mod c;

write(s mod c);

end.