f0(){ f$[$1<4] $1/2;: $[{{t=b,a=2*a}*b+a*a,{b=($1%2?(a+=t)-t:t),a=a}%10**9}];}
read i b&&a=1 f0 $[i+2]&&echo $b&&. *