#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

int n, sol, ok, a[14], v[14];

int abs(int k){
      if(k < 0)
            return -k;
      return k;
}

int verif(int poz, int x, int y){

      int ok2=1;

      for(int i=1;i<=poz && ok2==1;i++)
            if(v[i] == y || abs(x - i)==abs(y - v[i]))
                  ok2=0;

      return ok2;
}


void bk(int k){

      if(k > n){

            if(ok != 0){
                  ok=0;
                  for(int i=1; i<=n; i++)
                        fout<<v[i]<<" ";
            }
            sol++;
            return;
      }

      for(int i=1; i<=n; i++)
            if(a[i]==0 && verif(k-1, k, i) == 1){
                  a[i]=1;
                  v[k]=i;
                  bk(k+1);
                  a[i]=0;
            }
}

int main (){

      fin>>n;
      ok=1;

      bk(1);

      fout<<"\n";
      fout<<sol;
      return 0;
}