var n,p,t,k,pi:int64;

procedure calcul(var n,k:int64);
begin
if 2*k<=p then
             begin
             t:=n;
             n:=(n*n)mod 1999999973;
             pi:=k;
             k:=2*k;
             calcul(n,k);
             if k+pi<=p then
                        begin
                        n:=(n*t) mod 1999999973;
                        k:=k+pi;
                        end;
             end;
end;

begin
assign(input,'lgput.in');
assign(output,'lgput.out');
reset(input);
rewrite(output);
readln(n,p);k:=1;
calcul(n,k);
writeln(n);
close(input);
close(output);
end.