program damer;
 var t:array[1..100] of integer;
     col,maindig,secdig:array[0..200] of boolean; {1-inseamna ocupata}
     n,i,ans:integer;

 procedure tipar;
  var i:integer;
 begin
   for i:=1 to n do write(t[i],' ');
   writeln;
 end;

 procedure dame(k:integer);
   var i,j:integer;
        corect:boolean;
 begin
   if k=n+1 then begin
     if ans = 0 then tipar;
     inc(ans);
     end
          else
     for i:=t[k]+1 to n do
       if (not col[i] and not maindig[i-k+n-1] and not secdig[i+k])
         then begin
                     t[k]:=i;

                     col[i]:=true;
                     maindig[i-k+n-1]:=true;
                     secdig[i+k]:=true;

                     dame(k+1);

                     col[i]:=false;
                     maindig[i-k+n-1]:=false;
                     secdig[i+k]:=false;
              end;

   t[k]:=0;

 end;


 begin
   assign(input,'damesah.in');
   reset(input);
   assign(output,'damesah.out');
   rewrite(output);
   readln(n);
   dame(1);
   writeln(ans);
   close(output);
 end.