#include <iostream>
#include <fstream>
#include <cmath>
#define NUM 15
int col[NUM], nrs, prima, sol[NUM], n;
int queen[NUM],  main_diag[NUM * 2], sec_diag[NUM * 2];
using namespace std;
void copiere()
{
    for(int i = 0; i < n; ++i)
        sol[i] = queen[i] + 1;
}
void bkt(int l)
{
    if ( l == n )
    {
        if ( !nrs )
            copiere();
        ++nrs;
    }
    else
    {
        for ( int c = 0; c < n; c++ )
        {
            if ( !col[c] && !main_diag[c - l + n - 1] && !sec_diag[l + c] )
            {
                queen[l] = c;

                col[c] = main_diag[c - l + n - 1] = sec_diag[l + c] = 1;
                bkt(l + 1);
                col[c] = main_diag[c - l + n - 1] = sec_diag[l + c] = 0;
            }
        }
    }
}
int main()
{
    ifstream f("damesah.in");
    ofstream g("damesah.out");
    f >> n;
    bkt(0);
    for(int i = 0; i < n; ++i)
        g << sol[i] << " ";
    g << "\n" << nrs;
    f.close();
    g.close();
}