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

our $STEPMAXIMUM = 2;

my $stufenCount;
if (@ARGV) {$stufenCount = $ARGV[0]}
else {chomp($stufenCount = <>)}

sub treppenKnecht {
    my ($cur, $sol, $pos, $max) = @_;
    if ($pos == $max) {push(@$sol, join('', @$cur)); return 1}
    if ($pos > $max) {return 0}
    for my $step (1..$STEPMAXIMUM) {
        if (treppenKnecht([@$cur, $step], $sol, $pos+$step, $max)) {return 0}
    }
}

my @solutions;
treppenKnecht([], \@solutions, 0, $stufenCount);

foreach (@solutions) {print "$_\n"}