#include <fstream>
#define DMAX 15
using namespace std;
FILE * fin = fopen("damesah.in", "r");
FILE * fout = fopen("damesah.out", "w");

void gen(int);

int n;
int sol[DMAX];

bool exista;
int nrsol, solfin[DMAX];

bool coloana[DMAX], d_princ[2*DMAX], d_sec[2*DMAX];

int main()
{
    fscanf(fin, "%d", &n);
    gen(1);
    
    int i;
    for (i=1; i<=n; i++) fprintf(fout, "%d ", solfin[i]);
    fprintf(fout, "\n%d \n", nrsol);
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void gen(int lin)
{
    if (lin==n+1)
    {
        nrsol++;
        if (!exista)
        {
            int i;
            exista=1;
            for (i=1; i<=n; i++) solfin[i]=sol[i];
        }
        return;
    }
    
    int col;
    for (col=1; col<=n; col++)
        if (!coloana[col] && !d_princ[n-lin+col] && !d_sec[lin+col-1])
        {
            coloana[col]=1;
            d_princ[n-lin+col]=1;
            d_sec[lin+col-1]=1;
            sol[lin]=col;
            
            gen(lin+1);
            
            coloana[col]=0;
            d_princ[n-lin+col]=0;
            d_sec[lin+col-1]=0;
        }
}