var f:text;
    n,i,j:byte;
    sol:array[1..13]of byte;
    nrsol:longint;
    bun:boolean;
begin
assign(f,'damesah.in');
reset(f);
readln(f,n);
close(f);
assign(f,'damesah.out');
rewrite(f);
i:=1;sol[i]:=0;
nrsol:=0;
repeat
 while sol[i]<n do
  begin
   inc(sol[i]);bun:=true;
   for j:=1 to i-1 do
    if (sol[j]=sol[i])or(i-j=abs(sol[i]-sol[j]))then
     bun:=false;
   if bun then
    if i<=n then
     if i=n then
      begin
       inc(nrsol);
       if nrsol=1 then
        for j:=1 to n do
         write(f,sol[j],' ');
      end
            else
      begin
       inc(i);
       sol[i]:=0
      end;
  end;
 dec(i);
until i=0;
writeln(f);
writeln(f,nrsol);
close(f);
end.