#include <iostream>
#include <fstream>
using namespace std;
fstream f,g;
int x[20],diag1[20],diag2[20],used[20],sol,n, diag[20];
int a[20][20], b[20][20];
int diagonala( int j, int i) // verifica atacul pe diag
{
    if (diag1[a[i][j]] || diag2[b[i][j]])
        return 1;
    return 0;
}
void modificaDiag(int j, int i, int val )
{
    diag1[a[i][j]] = val;
    diag2[b[i][j]] = val;
}
void backtracking(int nr)
{
    for (int i = 1 ; i<= n; i++)
    {
        if (!used[i] &&  !diagonala(nr, i))
        {
            x[nr] = i;
            used[i] = 1;
            modificaDiag(nr,i,1);

            if (nr == n && sol > 0)
                sol++;

            if (nr == n && sol == 0)
            {
                for(int j = 1; j<=n ; j++)
                    g<<x[j]<<" ";
                sol = 1;
            }
            backtracking(nr + 1 );
            modificaDiag(nr,i,0);
            used[i] = 0;
        }
    }
}
int main()
{
    f.open("damesah.in",ios::in);
    g.open("damesah.out",ios::out);
    f>>n;
    int i, j;
   // cin>>n;
    for (i =1 ; i<=n; i++)
        a[1][i]=i;
    for (i =2 ; i<=n; i++)
        for (j = 1;  j<= n ; j++)
                a[i][j]= a[i-1][j]+1;

     for (i =1 ; i<=n; i++)
        b[n][i]=i;
    for (i =n-1 ; i>0; i--)
        for (j = 1;  j<= n ; j++)
                b[i][j]= b[i+1][j]+1;

    backtracking(1);
    g<<"\n"<<sol;
}