const q = 1999999973;
var n,p:int64;

    f,g:text;

function lgput(a:int64; b:int64):int64;
begin
	if b = 0 then begin lgput:=1; exit; end;
	if b = 1 then begin lgput:=a; exit; end;
	if b mod 2 = 0 then begin lgput := (lgput(a, b div 2)*lgput(a, b div 2)) mod q; exit; end;
	lgput := (lgput(a, (b-1) div 2)*lgput(a, (b-1) div 2)) mod q;
end;

begin
assign(f,'lgput.in');reset(f);
assign(g,'lgput.out');rewrite(g);
readln(f,n,p);

writeln(g,lgput(n,p));
close(g);

end.