#!perl -n
use bigint;
print ${fibo($_)}[0][0],$/;
sub fibo{
 my ($n)=@_;
 return [[1,1],[1,0]] if $n<2;
 return mx(fibo($n-1),fibo(0)) if $n%2==1;
 my $z=fibo(int($n/2));
 mx($z,$z);
}
sub mx{
 my ($a,$b)=@_;
 my @r=();
 for(my $i=0;$i<2;$i++){
  for(my $j=0;$j<2;$j++){
   $r[$i][$j] = (${$a}[0][$j]*${$b}[$i][0] + ${$a}[1][$j]*${$b}[$i][1])%(10**9);
  }
 }
 return \@r;
}