#include <cstdio>

using namespace std;

FILE *f, *g;

bool ok = 1, sol;

int n, k;

int cnt;

int lin[15], col[15];

int diag1[30], diag2[30];

int stk[15];

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

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

    fclose(f);
}

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

    int i;

    for(i = 1; i <= n; i ++)
        fprintf(g, "%d ", stk[i]);

    fprintf(g, "\n");
}


void backt(int k, int n)
{
    int c;

    if(k == n + 1)
    {
        if(ok == 1)
        {
            printFile();

            ok = 0;
        }

        cnt ++;
    }

    else
    {
        for(c = 1; c <= n; c ++)
        {
            if (col[c] == 0 && diag1[c - k + n] == 0 && diag2[k + c - 1] == 0)
            {
                stk[k] = c;

                col[c] = diag1[c - k + n] = diag2[k + c - 1] = true;

                backt(k + 1, n);

                col[c] = diag1[c - k + n] = diag2[k + c - 1] = false;

            }
        }
    }
}

void solve()
{
    backt(1, n);
}

void printResult()
{
    fprintf(g, "%d\n", cnt);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printResult();

    return 0;
}