#include <bits/stdc++.h>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int st[12], n, nr_afis;
char tabla[12][12];

int dx[] = { -1, -1 };
int dy[] = { -1, 1 };

void Init()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            tabla[i][j] = '-';
}

void Afisare()
{
    nr_afis++;
    if(nr_afis <= 1)
    {
        for (int i = 1; i <= n; i++)
            fout << st[i] << " ";
        fout << "\n";
    }
}

int Valid(int top)
{
    int k, x, y;
    for(int i = 1;i < top;i++)
        if(st[i] == st[top]) return 0;
    for (k = 0; k < 2; k++)
    {
        x = top;
        y = st[top];
        while (x > 0 && y > 0 && x < n + 1 && y < n + 1)
        {
            x += dx[k];
            y += dy[k];
            if (tabla[x][y] == '*') return 0;
        }
    }
    tabla[top][st[top]] = '*';
    return 1;
}

void Remove(int top)
{
    for (int i = 1; i <= n; i++)
        if (tabla[top][i] == '*')
            tabla[top][i] = '-';
}

void Back()
{
    int top, cand;
    top = 0;
    st[++top] = 0;
    while (top > 0)
    {
        cand = 0;
        while (cand == 0 && st[top] < n)
        {
            st[top]++;
            cand = Valid(top);
        }
        if (cand == 0)
        {
            top--;
            Remove(top);
        }
        else if (top == n) Afisare();
        else st[++top] = 0;
    }
}

int main()
{
    fin >> n;
    Init();
    Back();
    fout << nr_afis << "\n";
    fin.close();
    fout.close();
}