#include <fstream>
#include <iostream>

using namespace std;

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

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

bool control(int x,int y)
{

  //sus
   for (int i=x;i>0;i--) if (a[i][y] == 1 ) return false;
   // diagonala stinga
      int i =x; int j =y;
    for (; i>0 && j>0;i-- , j-- ) if (a[i][j] == 1 ) return false;
  // diagonala dreapta
   i =x; j =y;
    for (; i>0 && j<=n;i-- , j++ ) if (a[i][j] == 1 ) return false;

   return true;

}

 void generare(int k)
 {

     if (k == n+1)
     {
         if (!ok)
         {
             for(int i=1;i<=n;i++)
              for (int j=1; j<=n;j++)
                if (a[i][j] == 1) sol[i] = j ;
                    ok =true;
         }
       m++;
     }
      else
      {
        for (int i=1;i<=n;i++)
        {
            if (control(k,i))
            {
                 a[k][i] = 1;
                 generare(k+1);
                 a[k][i] = 0;
            }
        }
      }
 }

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

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


    return 0;
}