#include <fstream>
#include <iostream>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

long n,m = 0;
int a[15];
bool ok = false;
bool col[15] , sec_diag[15] , main_diag[15];

 void generare(int k)
 {

     if (k == n)
     {
         if (!ok)
         {
             for(int i=0;i<n;i++) g << a[i] + 1 << " " ;
                    ok =true;
         }
       m++;
     }
      else
      {
        for (int i=0;i<n;i++)
        {
            if (!col[i] && !sec_diag[i + k - 1] && !main_diag[i - k + n - 1] )
            {
                 a[k] = i;
                 col[i] = sec_diag[i+k-1] = main_diag[i-k+n-1] = true;
                 generare(k+1);
                 col[i] = sec_diag[i+k-1] = main_diag[i-k+n-1] = false;
            }
        }
      }
 }

int main()
{
    f >> n;
    generare(0);

        g << "\n";
    g << m << "\n";


    return 0;
}