use strict;use POSIX qw(floor);use Math::BigInt lib=>"Calc";my$cl=16;sub car{no strict"vars";my$x=shift();my$car=0;$main::{x_for_car}=$x;for(my$xidx=0;$xidx<=$#x_for_car;$xidx++){$x_for_car[$xidx]+=$car;$car=floor($x_for_car[$xidx]/1e9);$x_for_car[$xidx]-=1e9*$car;}push(@$x,$car)if$car;}sub emm{(my$x,my$y)=@_;if(($#{$x->{"value"}}<=$#{$y->{"value"}}?$#{$x->{"value"}}:$#{$y->{"value"}})<180){my$sxv=$x->{"value"};my$syv=$y->{"value"};my@to_be_rv=();my$nc=$cl;for(my$xoff=0;$xoff<=$#$sxv;$xoff++){my$base_idx=$xoff;for my$ydigit(@$syv){$to_be_rv[$base_idx++]+=$$sxv[$xoff]*$ydigit;}$nc--;if($nc<=0){car(\@to_be_rv);$nc=$cl;}}car(\@to_be_rv);return bless({"value"=>\@to_be_rv,sign=>"+"},"Math::BigInt");}(my$mindigits,my$maxdigits)=$x->length<=$y->length?(scalar($x->length),scalar($y->length)):(scalar($y->length),scalar($x->length));my$low=$mindigits-1;my$high=int($maxdigits/2);my$b=$low<=$high?$low:$high;my$x1=Math::BigInt->new(substr($x->bstr,0,$x->length-$b));my$y1=Math::BigInt->new(substr($y->bstr,0,$y->length-$b));my$x0=Math::BigInt->new(substr($x->bstr,$x->length-$b,$b));my$y0=Math::BigInt->new(substr($y->bstr,$y->length-$b,$b));my$x1y1=emm($x1,$y1);my$x0y0=emm($x0,$y0);return(Math::BigInt->new($x1y1->bstr.("0"x($b*2))))+(Math::BigInt->new((emm(($x1+$x0),($y1+$y0))-$x1y1-$x0y0)->bstr.("0"x$b)))+$x0y0;}my@elem=map({Math::BigInt->new($_)}(0,1,0));for(3..37){$cl=((100)x29,62,60,54,58,53,52,51,52,49)[$_];$elem[$_]=emm($elem[$_-1],$elem[$_-3])+1;}print($elem[37]->bstr());