// Problema damelor
#include <stdio.h>
#include <stdlib.h>
#define MAX 13

void init(int v[], int k)
{
    v[k] = -1;
}

int succesor(int v[], int k, int n)
{
    int as = 0;
    if(v[k] < n - 1)
    {
        v[k]++;
        as = 1;
    }
    return as;
}

int valid(int v[], int k, int n)
{
    int i;
    // aceeasi coloana
    for(i = 0; i < k; i++)
        if(v[i] == v[k])
            return 0;
    // aceeasi diagonala
    for(i = 0; i < k; i++)
        if(k - i == v[k] - v[i])
            return 0;
    for(i = 0; i < k; i++)
        if(i + v[i] == k + v[k])
            return 0;
    return 1;
}
int solutie(int k, int n)
{
    if(k == n - 1)
        return 1;
    else
        return 0;
}

void tipar(FILE *g, int v[], int n)
{
    int i;
    for(i = 0; i < n; i++)
        fprintf(g, "%d ", v[i] + 1);
    fprintf(g, "\n");
}

void dame(int n)
{
    int v[MAX] = {0};
    int k = 0, as, ev;
    int nrSolutii = 0;
    FILE *g;


    g = fopen("damesah.out", "w");



    init(v, k);
    while(k >= 0)
    {
        do
        {
            as = succesor(v, k, n);
            if(as)
                ev = valid(v, k, n);
        }while(as && !ev);
        if(as)
        {
            if(solutie(k, n))
            {
                nrSolutii++;
                if(nrSolutii == 1)
                    tipar(g, v, n);
            }
            else
            {
                k++;
                init(v, k);
            }
        }
        else
            k--;
    }
    fprintf(g, "%d", nrSolutii);
    fclose(g);
}

int main()
{
    FILE *f;
    int n;

    f = fopen("damesah.in", "r");

    fscanf(f, "%d", &n);
    fclose(f);

    dame(n);

    return 0;
}