#!/usr/bin/perl -w
use strict;
use Memoize;

my $n = $ARGV[0];

sub fibword {
  my $n = shift;
  return "0" if $n == 1;
  return "1" if $n == 2;
  return fibword($n-1) . fibword($n-2);
} memoize 'fibword';

##########################
# Commented out: Too slow! The version below is much faster.

#sub subseqs {
#  my $n = shift;
#  return ("0", "1") if $n == 1;
#  my $word = fibword($n+3);
#  my @rv;
#  for my $seq (subseqs($n-1)) {
#    push @rv, $seq."0" if $word =~ m/@{[$seq."0"]}/;
#    push @rv, $seq."1" if $word =~ m/@{[$seq."1"]}/;
#  }
#  warn "Not all subsequences found!" if @rv < $n+1;
#  warn "Too many subsequences found!" if @rv > $n+1;
#  return @rv;
#} memoize 'subseqsold';
##########################

# The "forbidden factors" technique used here appears in Mignosi et
# al., "Words and forbidden factors".

sub subseqs {
  my $n = shift;
  my @rv;
  return ("0", "1") if $n == 1;
  my @forbidden = map {qr/$_/} forbiddenfactors(log($n)/log(1.618) +3);
  my @seqs = map {$_ . "0", $_ . "1"} subseqs($n-1);
  SEQ: for my $seq (@seqs) {
    for my $factor (@forbidden) {
      next SEQ if $seq =~ $factor;
    }
    push @rv, $seq;
  }

  # these warnings should never ever happen
  warn "Not all subsequences found!" if @rv < $n+1;
  warn "Too many subsequences found!" if @rv > $n+1;
  return @rv;
} memoize 'subseqs';


sub forbiddenfactors {
  my $n = shift;
  my @rv;
  for my $i (3..$n) {
    my $palindrome = substr(fibword($i), 0, -2);
    if ($i % 2) {
      push @rv, "0" . $palindrome . "0";
    }
    else {
      push @rv, "1" . $palindrome . "1";
    }
  }
  return @rv;
}

sub maketree {
  # Symbol decoding:
  # 0 = 0, with downward branch
  # 1 = 0, with rightward branch
  # 2 = 0, with dual branch
  # 3 = 1, with down branch
  # 4 = 1, with right branch
  # 5 = 1, with dual branch
  # 6 = upper left corner.
  my $n = shift;
  my @symbol = ("0", "0", "0", "1", "1", "1", "0");
  my $table = [[$symbol[6]]];
  for my $d (1..$n) {
    my $i = 0;
    my @nextlevel = subseqs($d+1);
    my $branched = 0;
    for my $seq (subseqs($d)) {
      my ($zero, $one) = (0,0);
      if (grep {$_ eq $seq."0"} @nextlevel) {
	$zero = 1;
      }
      if (grep {$_ eq $seq."1"} @nextlevel) {
	$one = 1;
      }

      if ($zero == 1 and $one == 1) {
	$branched = 1;
	$table->[$d-$i][$i] = $symbol[2] if substr($seq, -1) eq "0";
	$table->[$d-$i][$i] = $symbol[5] if substr($seq, -1) eq "1";
      }
      elsif ($branched) {
	$table->[$d-$i][$i] = $symbol[1] if substr($seq, -1) eq "0";
	$table->[$d-$i][$i] = $symbol[4] if substr($seq, -1) eq "1";
      }
      else {
	$table->[$d-$i][$i] = $symbol[0] if substr($seq, -1) eq "0";
	$table->[$d-$i][$i] = $symbol[3] if substr($seq, -1) eq "1";
      }

      ++$i;
    }
  }
  return $table;
}

print "P1\n";
print "@{[$n+1]} @{[$n+1]}\n";
for (@{maketree($n)}) {
  my $string = join(" ", @$_);
  print join " ", ($string, join " ", (split "", "0" x ($n - (length($string)-1)/2)));
  print "\n";
}
