#include <cstdio>

using namespace std;

int nrSolutii, v[14], diagonaleDinStanga[30], diagonaleDinDreapta[30], linie[14];

void backtracking(int nivel, int n, FILE* out)
{
    if (nivel == n + 1)
    {
        nrSolutii++;
        if (nrSolutii == 1)
        {
            for (int i = 1 ; i <= n ; i++)
                fprintf(out,"%d ",v[i]);
            fprintf(out,"\n");
        }
    }
    else
    {
        // iau toate pozitiile pe care le poate lua dama de pe linia nivel
        for (int i = 1 ; i <= n ; i++)
        {
            int j = i; // pentru codul de mai jos
            if (diagonaleDinStanga[(j - nivel) + n] == 0 && diagonaleDinDreapta[nivel + j] == 0 && linie[j] == 0)
            {
                v[nivel] = j;
                diagonaleDinStanga[(j - nivel) + n] = 1;
                diagonaleDinDreapta[nivel + j] = 1;
                linie[j] = 1;

                backtracking(nivel + 1,n,out);

                linie[j] = 0;
                diagonaleDinDreapta[nivel + j] = 0;
                diagonaleDinStanga[(j - nivel) + n] = 0;
                v[nivel] = 0;
            }
        }
    }
}

int main()
{
    FILE* in = fopen("damesah.in","r");
    FILE* out = fopen("damesah.out","w");

    int n(0);
    fscanf(in,"%d",&n);
    backtracking(1,n,out);
    fprintf(out,"%d",nrSolutii);
    return 0;
}