#include <iostream>
#include <fstream>
#define Nmax 14
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");
int nrTotalSolutii;
int b[Nmax];
int diag_principala[Nmax *3],diag_secundara[Nmax*3];
int viz[Nmax];
int n;

void afisareSolutii ()
{
    int i;
    for (i = 1; i <= n; i++)
        fout<<b[i]<<" ";
       // fout<<"\n";
        nrTotalSolutii++;
   // for (i = 1; i <= n*3; i++)
     //   fout<<diag_principala[i]<<" ";

}
void Back (int k ) // k semnifica linia curenta
{

    for (int i =1; i<= n;i++)
        if (viz[i] == 0 && diag_principala[k-i+n]==0 && diag_secundara[i+k]==0)
    {
        b[k] = i;

        diag_principala[k-i+n] = 1;
        diag_secundara[i+k] = 1;
        viz[i] = 1;
        if (k < n) Back(k+1);
        else if (k == n && nrTotalSolutii ==0 ) afisareSolutii();
        else if (k ==n) nrTotalSolutii++;


        diag_principala[k-i+n] = 0;
        diag_secundara[i+k] = 0;
        viz[i] = 0;
    }

}
int main()
{
    fin>>n;
    Back(1);
    fout<<"\n"<<nrTotalSolutii;
    return 0;
}