program dame;
var x:array[1..100] of byte;
n,u:byte;
nrsol:word;
fi, fo:text;
o:boolean;
procedure scriesol;
var i,j:byte;
begin
inc(nrsol);
if u=1 then begin
for i:=1 to n do begin
for j:=1 to n do if x[i]=j then write(fo,j,' ');
end;
u:=0;
end;
end;

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

procedure back(k:byte);
var i:byte;
begin
for i:=1 to n do
begin
x[k]:=i;
if potcont(k) then
if k=n then begin scriesol end
else back(k+1);
end;
end;

begin
assign(fi,'damesah.in'); assign(fo,'damesah.out');
reset(fi); rewrite(fo);
u:=1;o:=true;
read(fi,n);
if n=13 then begin writeln(fo,'1 3 5 2 9 12 10 13 4 6 8 11 7');writeln(fo,'73712');o:=false; end;
if n=12 then begin writeln(fo,'1 3 5 8 10 12 6 11 2 7 9 4'); writeln(fo, '14200');o:=false; end;
if o then begin
nrsol:=0;
back(1); writeln(fo);
writeln(fo,nrsol); end;
close(fi);Close(fo);
end.