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

var n,rs:longint;
    u:byte;
    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 then begin
                     inc(rs);
                     if u=0 then begin
                                  for i:=1 to n do
                                   write(a[i],' ');
                                    writeln;
                                 end;
                     u:=1;
                    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);
  dame(1);
  writeln(rs);

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