program problema_damelor;
var     nr,i,n:integer;
        x,v:array[1..100] of integer;

procedure tipar;
var       i:integer;
begin
  inc(nr);
  if nr=1 then
    for i:=1 to n do
      v[i]:=x[i];
end;


function cont(k:integer):boolean;
var      i:integer;
begin
  cont:=true;
  for i:=1 to k-1 do
    if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
      cont:=false;
end;

procedure bkt;
var       k:integer;
begin
   k:=1;
   x[k]:=0;
   while k>0 do
     if x[k]<n then
       begin
         x[k]:=x[k]+1;
         if cont(k) then
           if k=n then tipar
             else
               begin
                 inc(k);
                 x[k]:=0;
               end;
       end
     else
       dec(k);
end;

begin
  assign(input,'damesah.in'); reset(input);
  assign(output,'damesah.out'); rewrite(output);
  readln(n);
  bkt;
  for i:=1 to n do
    write(v[i],' ');
  writeln(nr);
  close(input);
  close(output);
end.