Program ridic_logaritmic;
const mk=1999999973;
var fi,fo : text;
    a,p,sol : qword; i,m : longword;

begin
    assign(fi,'lgput.in'); reset(fi); read(fi,a,p);
    assign(fo,'lgput.out'); rewrite(fo);
    sol:=1; m:=0;
    while (1 shl m)<p do m:=m+1;

    for i:=0 to m do begin
                     if p and (1 shl i)>0 then sol:=(sol*a) mod mk;
                     a:=(a*a) mod mk;
                     end;
    write(fo,sol);
    close(fi); close(fo);
end.