#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 13;
int v[NMAX + 5], cnt, n, lin[NMAX + 5], col[NMAX + 5], mat[NMAX + 5][NMAX + 5];
bool fr[NMAX + 5], ok;

bool Diag(int x, int y)
{
    int l = x, c = y;

    while(--l >= 1 and --c >= 1)
        if(mat[l][c] == 1)
            return false;

    l = x, c = y;

    while(--l >= 1 and ++c >= n)
        if(mat[l][c] == 1)
            return false;

    l = x, c = y;

    while(++l <= n and --c >= 1)
        if(mat[l][c] == 1)
            return false;

    l = x, c = y;

    while(++l <= n and ++c <= n)
        if(mat[l][c] == 1)
            return false;

    return true;
}

bool verify()
{
    memset(mat, 0, sizeof mat);
    memset(lin, 0, sizeof lin);
    memset(col, 0, sizeof col);

    for(int i = 1; i <= n; i++)
        mat[i][v[i]] = 1;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            lin[i] += mat[i][j];
            col[j] += mat[j][i];
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(mat[i][j] == 1)
                if(Diag(i, j) == false)
                    return false;

    for(int i = 1; i <= n; i++)
        if(lin[i] != 1 or col[i] != 1)
            return false;

    return true;
}

void Print()
{
    for(int i = 1; i <= n; i++)
        fout << v[i] << ' ';
    fout << '\n';
}

void bkt(int k)
{
    if(k == n + 1)
    {
        if(verify() == true)
        {
            if(ok == 0)
            {
                Print();
                ok = 1;
            }

            cnt++;
        }

        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(fr[i] == 0)
        {
            v[k] = i;
            fr[i] = 1;

            bkt(k + 1);
            fr[i] = 0;
        }
    }
}

int main()
{
    fin >> n;

    bkt(1);

    fout << cnt;
    fin.close();
    fout.close();
    return 0;
}