#!perl -pl
sub f{($x,$y)=($n=$_[0])?$n&1?(f($n-1)+$y,$x):(f($n/2)**2+$y**2,$y*(2*$x-$y)%1e9):1;$x%=1e9}$_=f$_