use bigint;
use constant M,129402307;
print f(<>%M,<>);
sub f{
	my($n,$m)=@_;
	$m&1?$m>1?f($n,$m-1)*$n%M:$n:f($n*$n%M,$m/2);
}