#!perl -pl
sub h{$h{local$_=++$_>>1}//=$_<5||(&h*&h+&h*&h)%1e9}$_=h$_+=$_+5