#!/usr/local/bin/perl
use strict;
use warnings;

my %cache;
sub f {
    my $n = shift;
    return 0 if $n == 0;
    return 1 if $n == 1;
    return $cache{$n} if exists $cache{$n};
    my $res = f($n - 1) + f($n - 2);
    $cache{$n} = $res;
    return $res;
}

print f(1);