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