var n,k,nrSol:integer;
    v:array[1..20] of integer;

function valid(k:integer):boolean;
  var i,j:integer;
  begin
   valid:=true;
   for i:=1 to k-1 do
   for j:=i+1 to k do
   if v[i]=v[j] then valid:=false;

   for i:=2 to k do
    begin
    if v[i]=v[i-1]+1 then valid:=false;
    if v[i]=v[i-1]-1 then valid:=false;
    end;

  end;

function solutie(k:integer):boolean;

 begin
   solutie:=true;
   if k<>n then solutie:=false;
   if solutie=true then inc(NrSol);


 end;

procedure afisare(k:integer);
var i:integer;
 begin
  for i:=1 to k do write(output,v[i],' ');
  writeln;

 end;


procedure back(k:integer);
var i:integer;
  begin
     for i:=1 to n do
       begin
         v[k]:=i;
         if (valid(k)) then
          begin
            if (solutie(k)) and (nrSol=1)  then afisare(k)
            else
            back(k+1);
          end;


       end;



  end;


Begin
     assign(input,''); reset(input);
     assign(output,''); rewrite(output);
     nrSol:=0;
     readln(input,n);
     back(1);
     write(output,nrSol);
     close(input);
     close(output);

end.