#!perl -p
sub f{$$m{local$_=++$_>>1}//=($_<5?$_/3:&f*&f+&f*&f)%$m}for$m(2e9+16,1e9+7){$_=f$_+=$_+3}