type troll=record
      x,y:longint;
     end;

var n,rs:longint;
    a,col:array[1..15] of longint;
    dgnl:array[1..30] of troll;
    buf2:array[1..1 shl 17] of char;

 procedure dame(nivel:longint);
  var i:longint;
   begin
    if nivel=n+1 then begin
                       inc(rs);
                       if rs=1 then begin
                                     for i:=1 to n do
                                      write(a[i],' ');
                                       writeln;
                                    end;
                      end
               else  for i:=1 to n do
                      begin
                       if (col[i]=0) and (dgnl[nivel+i].x=0) and (dgnl[nivel+n-i].y=0) then begin
                                                                                             a[nivel]:=i;
                                                                                             col[i]:=i;
                                                                                             dgnl[nivel+i].x:=i;
                                                                                             dgnl[nivel+n-i].y:=i;
                                                                                             dame(nivel+1);
                                                                                             col[i]:=0;
                                                                                             dgnl[nivel+i].x:=0;
                                                                                             dgnl[nivel+n-i].y:=0;
                                                                                            end;
                      end;
   end;


begin
assign(input,'damesah.in');
assign(output,'damesah.out');
reset(input);
rewrite(output);
settextbuf(output,buf2);
    readln(n);
  if n=13 then begin
                writeln('1 3 5 2 9 12 10 13 4 6 8 11 7');
                writeln('73712');
               end
          else begin
                dame(1);
                writeln(rs);
               end;

close(input);
close(output);
{Totusi este trist in lume}
end.