program day4_1;

 const
  sushu:array[1..100] of integer=(0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,
                                  0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0
                                  ,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1
                                 ,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0);
 var
     n,i:integer;
     total:longint;
     used:array[1..50] of boolean;
     a:array[0..50] of integer;
     can:array[1..50,0..50] of integer;

 procedure init;
  var
     i,j:integer;
 begin
  read(n);
  for i:=1 to n do
   for j:=1 to n do
   if sushu[i+j]=1
   then
       begin
       inc(can[i,0]);
       can[i,can[i,0]]:=j
       end;
 end;

 procedure print;
  var
     i:integer;
 begin
  inc(total);
  for i:=1 to n-1 do
  write(a[i],' ');
  writeln(a[n]);
 end;

 procedure search(k:integer);
  var
     i,V:integer;
 begin
  if k>n then begin print; exit end;

  for i:=1 to can[a[k-1],0] do
   begin
   V:=can[a[k-1],i];
   if not used[V]
   then
       begin
       a[k]:=V;
       used[V]:=true;
       search(k+1);
       used[V]:=false;
       a[k]:=0
       end;
   end;

 end;

 begin
  assign(input,'dfs3.in');
  assign(output,'dfs3.out');
  reset(input); rewrite(output);
  init;
  if n=1 then begin writeln(0); close(input); close(output); halt end;
  for i:=1 to n do
   begin
   fillchar(used,sizeof(used),0);
   used[i]:=true;
   a[1]:=i;
   search(2);
   end;
  writeln(total);
  close(input); close(output);
 end.