use bigint;

my @fib    = (1,1); # Fibonacci(n+1)
my @primes = ();	# primes dividing n
my $max    = 1000;

foreach my $n (2..$max) {
	$fib[$n] = $fib[$n-1] + $fib[$n-2];
	if (not $primes[$n]) {
		my $m = $n;
		while ($m <= $max) {
			push @{$primes[$m]} => $n;
			$m += $n;
		}
	}
}

sub a {
	my $n = shift;
	my @primes = @{$primes[$n]};
	if ($n==$primes[0]) {
		# prime number
		return $fib[$n] - 1;
	} else {
		# non prime number
		my $bit   = 1;
		my @split = ();
		foreach my $prime (@primes) {
			push @split => map { { "pos" => $n/$prime*$_,
								   "bit" => $bit,
								   "lst" => $_==$prime-1 } } 1..$prime-1;
			$bit <<= 1;
		}

		@split = sort { $a->{pos} <=> $b->{pos} } @split;

		# mask -> pos -> count
		my %state = ();
		$state{0}{0} = 1;
		
		foreach my $split (@split) {
			my $pos = $split->{pos};
			my $bit = $split->{bit};
			my $lst = $split->{lst};

			my %newstate = ();

			foreach my $mask (keys %state) {
				my $newmask = $mask | $bit;
				foreach my $wpos (keys %{$state{$mask}}) {
					my $cnt = $state{$mask}{$wpos};

					if ($mask & $bit) {
						$newstate{$mask}{$wpos} += $cnt;
					} else {
						# put 2x1 brick
						# ...-+--.--+-...
						#     |     |
						# ...-+--.--+-...
						{
							if ($wpos <= $pos-1) {
								$newstate{$newmask}{$pos+1} += $cnt * $fib[$pos-1-$wpos];
							}
						}

						# force a split ?
						#    ...-+-...
						#        |
						#    ...-+-...
						if (!$lst) {
							if ($wpos <= $pos) {
								$newstate{$mask}{$pos} += $cnt * $fib[$pos-$wpos];
							}
						}
					}
				}
			}

			%state = %newstate;
		}

		my $total = 0;

		foreach my $mask (keys %state) {
			foreach my $wpos (keys %{$state{$mask}}) {
				my $cnt = $state{$mask}{$wpos};
				# print "$mask -> $wpos $cnt\n";
				$total += $cnt * $fib[$n - $wpos];
			}
		}

		return $total;
	}
}

foreach my $n (1..$max) {
	my $a = a($n);
	print "a($n)=$a\n";
}