var n,rs:longint;
    a,col:array[1..15] of longint;
    x,y:array[1..30] of longint;
    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 (x[nivel+i]=0) and (y[nivel+n-i]=0) then begin
                                                                                   a[nivel]:=i;
                                                                                   col[i]:=i;
                                                                                   x[nivel+i]:=i;
                                                                                   y[nivel+n-i]:=i;
                                                                                   dame(nivel+1);
                                                                                   col[i]:=0;
                                                                                   x[nivel+i]:=0;
                                                                                   y[nivel+n-i]:=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.