#include <stdio.h>
#include <stdlib.h>
FILE *fout;
int frecv[50], diags[50], diagp[100], v[50], tot, cat;
#define diagp (diagp+50)

void func(int pos, int n){
  int i;
  if(pos==n){
    ++tot;
    if(cat<1){
      ++cat;
      for(i=0; i<n; i++)
        fprintf(fout, "%d ", v[i]+1);
      fprintf(fout, "\n");
    }
  } else
    for(i=0; i<n; i++)
      if(frecv[i]==0 && diags[pos+i]==0 && diagp[i-pos]==0){
        frecv[i]=1; diags[pos+i]=1; diagp[i-pos]=1;
        v[pos]=i;
        func(pos+1, n);
        frecv[i]=0; diags[pos+i]=0; diagp[i-pos]=0;
      }
}

int main()
{
    FILE *fin;
    int n;
    fin=fopen("damesah.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
    fout=fopen("damesah.out", "w");
    func(0, n);
    fprintf(fout, "%d\n", tot);
    fclose(fout);
    return 0;
}