#include <fstream>

using namespace std;

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

int n, sol;
bool praf, Col[16], Diag1[32], Diag2[32]; // praf - se verifica daca prima varianta a fost afisata
int poz[16];

void genereaza(int k)
{
    if (k == n+1)
    {
        if (!praf)
        {
            for (int i = 1; i <= n; i++)
                g << poz[i] << " ";
            praf = true;
        }
        sol++;
    }
    else for (int i = 1; i <= n; i++)
        if (!Col[i] && !Diag1[n-k+i] && !Diag2[k+i-1])
        {
            poz[k] = i;
            Col[i] = Diag1[n-k+i] = Diag2[k+i-1] = true;
            genereaza(k+1);
            Col[i] = Diag1[n-k+i] = Diag2[k+i-1] = false;
        }
}

int main()
{
    f >> n;
    genereaza(1);
    g << "\n" << sol;
    return 0;
}