#include <fstream>
#include <bitset>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
const int NMAX = 13;
bitset<NMAX+5>coloane;
bitset<NMAX+5>diagoanala_principala;
bitset<NMAX+5>diagonala_secundara;
///Pentru diagoanala principala vom calcula diagonala pe care se afla dama cu formula linie - coloana + n
///Pentru diagoanala secundara vom calcula diagonala pe care se afla dama cu formula linie + coloana -1
int n, nr_sol;
int sol[NMAX+5];
void print()
{
    nr_sol++;
  if(nr_sol ==1)
  {
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<" ";
    fout<<"\n";
  }
}
void backt(int k)
{
   if(k == n+1)
     print();
   else
   {
      for(int i=1;i<=n;i++)
      {
         if(coloane[i]==0 && diagoanala_principala[k - i + n] ==0 && diagonala_secundara[i+k-1]==0)
         {
           coloane[i] =1;
           sol[k] = i;
           diagoanala_principala[k-i+n] =1;
           diagonala_secundara[i+k-1] =1;
           backt(k+1);
           sol[k] = 0;
           coloane[i] = 0;
           diagoanala_principala[k-i+n] =0;
           diagonala_secundara[i+k-1]=0;
         }
      }
   }
}
int main()
{
    fin>>n;
    backt(1);
    fout<<nr_sol<<"\n";
    return 0;
}