#include <stdio.h>
#include <stdlib.h>
  FILE*fin;
  FILE*fout;
int v[13],n,s = 0;
int mod(int a){
  if(a < 0) return -a;
  else return a;
}
int valid(int k){
  int i;

  for(i = 1; i < k;i++)
    if((v[k] == v[i]) || (k-i == mod(v[k] - v[i])))
      return 0;
  return 1;
}
int fol(int k){
  for(int i = 1; i < k; i++)
    if(v[k] == v[i])
      return 0;
  return 1;
}
void back (int k){
  for(int i=1; i<=n ; i++){
    v[k] = i;
    if( fol(k)){
      if(k == n && valid(k)){
        if(s == 0){
          for(int j = 1; j <= n;j++)
            fprintf(fout,"%d ",v[j]);
          fprintf(fout,"\n");}
        s++;
      }
      else if(valid(k))
        back( k + 1 );
    }
  }
}
int main()
{

  fin =fopen("damesah.in","r");
  fout = fopen("damesah.out","w");
  fscanf(fin,"%d",&n);
  back(1);
  fprintf(fout,"%d",s);
  return 0;
}