Program dame;
var f,q:text;
    a:array[1..13] of byte;
    n,nr:byte;
procedure tpar;
var i:integer;
begin
        for i:=1 to n do write(q,a[i],' ');
        writeln(q);
end;
function valid(k:integer):boolean;
var i:integer;
begin
        valid:=true;
        for i:=1 to k-1 do if a[i]=a[k] then valid:=false;
        if k>=2 then
        if abs(a[k]-a[k-1])<=1 then valid:=false;
end;
procedure back(k:integer);
var i:integer;
begin
        if k<=n then
        begin
                for i:=1 to n do begin a[k]:=i; if valid(k) then back(k+1); end;
        end
        else begin inc(nr); if nr=1 then tpar; end;
end;
begin
assign(f,'damesah.in');
reset(F);
assign(q,'damesah.out');
rewrite(q);
readln(f,n);
back(1);
write(q,nr);
close(F);
close(q);
end.