var t:array[1..15] of integer;
    n,i,c,p,k,x:integer;
begin
assign(input,'damesah.in'); reset(input);
assign(output,'damesah.out'); rewrite(output);
readln(n);
k:=1; t[k]:=0;
while k>0 do
 begin
  repeat
   p:=0; c:=0;
   if t[k]<n then
    begin
     p:=1;
     inc(t[k])
    end;
   for i:=1 to k-1 do
    begin
     if (t[i]=t[k]) or (abs(i-k)=abs(t[i]-t[k])) then inc(c);
     if c>0 then break
    end
  until ((p=1) and (c=0)) or (p=0);
  if (k=n) and (p=1) and (c=0) then
   begin
    inc(x);
    if x=1 then
     begin
      for i:=1 to n do write(t[i],' ');
      writeln
     end
   end else
  if (k<n) and (p=1) and (c=0) then
   begin
    inc(k);
    t[k]:=0
   end
  else dec(k)
 end;
writeln(x);
close(input);
close(output)
end.