#include <fstream>
#include <iostream>

using namespace std;

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

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

 void generare(int k)
 {

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

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

    for (int i=1;i<=n;i++)
        g << sol[i] << " ";
        g << "\n";
    g << m << "\n";


    return 0;
}