#include <fstream>
#include <vector>;
using namespace std;
vector<int>permutare;
vector<bool>folosit;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int diagonala1[40];
int diagonala2[40];
   int n;
   bool ok=false;
   int raspuns=0;
void backtracking(int linie){
    if(linie==n+1){
        raspuns++;
        if(ok==false){
        for(int i=1;i<=n;i++){
            fout<<permutare[i]<<" ";
        }
        }
        ok=true;
        return;
    }
  for(int coloana=1;coloana<=n;coloana++){
    if(folosit[coloana] || diagonala1[linie-coloana+n] ||diagonala2[linie+coloana]){
        continue;
    }
    folosit[coloana]=true;
    diagonala1[linie-coloana+n]=true;
    diagonala2[linie+coloana]=true;
    permutare[linie]=coloana;
    backtracking(linie+1);
    folosit[coloana]=false;
    diagonala1[linie-coloana+n]=false;
    diagonala2[linie+coloana]=false;
  }

}
int main()
{
   fin>>n;
   permutare.resize(n+1,0);
   folosit.resize(n+1,false);
   backtracking(1);
   fout<<'\n';
   fout<<raspuns;
    return 0;
}