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

my @adapters;
while (<ARGV>) {
    chomp;
    push(@adapters, $_);
}

# reverse!
@adapters = sort { $b <=> $a } (@adapters, 0);

# Consider 1 2 3 4 5 6
# set n(9) = 1
# 6 -> n(9)        # 1
# 5 -> n(6)        # 1
# 4 -> n(5) + n(6) # 2
# 3 -> n(4) + n(5) + n(6) # 4
# 2 -> n(3) + n(4) + n(5) # 7
# 1 -> n(2) + n(3) + n(4) # 13

my %H;
$H{$adapters[0] + 3} = 1; # device
while (@adapters) {
    my $n = shift(@adapters);
    # how many things can you get to?
    my $total;
    for (my $i = $n + 1; $i <= $n + 3; $i++) {
        if (exists($H{$i})) {
            $total += $H{$i};
        }
    }
    $H{$n} = $total;
}
print "$H{0}\n";
