program MayLava;
const
 ss:array[1..24]of integer=(3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97);
var
 a:array[1..50]of boolean;
 num:array[1..50]of integer;
 n,sum:longint;
 fout:text;
procedure start;
 var
  f:text;
 begin
  assign(f,'dfs3.in');
  reset(f);
  readln(f,n);
  close(f);
  fillchar(a,sizeof(a),true);
  sum:=0;
 end;
procedure hunt(x:integer);
 var
  i:longint;
 begin
  if x>n then begin
   inc(sum);
   for i:=1 to n-1 do
    write(fout,num[i],' ');
   writeln(fout,num[n]);
   exit;
  end;
  for i:=1 to 24 do
   if (ss[i]-num[x-1]>0) and (ss[i]-num[x-1]<=n) and (a[ss[i]-num[x-1]]) then begin
    num[x]:=ss[i]-num[x-1];
    a[ss[i]-num[x-1]]:=false;
    hunt(x+1);
    a[ss[i]-num[x-1]]:=true;
   end;
 end;
procedure main;
 var
  i:integer;
 begin
  assign(fout,'dfs3.out');
  rewrite(fout);
  for i:=1 to n do begin
   num[1]:=i;
   a[i]:=false;
   hunt(2);
   a[i]:=true;
  end;
  writeln(fout,sum);
  close(fout);
 end;
{=======MAIN========}
BEGIN
 start;
 main;
END.