#include <fstream>

using namespace std;

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

const int NMAX = 13;

int N;

int st[NMAX + 3], nrSol;
bool d[NMAX + 3];

bool foundSol = false;

void Push_Sol()
{
    if(!foundSol)
    {
        foundSol = true;

        for(int i = 1; i <= N; i++)
            fout << st[i] << ' ';

        fout << '\n';
    }

    nrSol++;
}

int ABS(int x)
{
    return max(x, -x);
}

bool Check_Diagonals(int p)
{
    for(int i = 1; i < p; i++)
        if(ABS(p - i) == ABS(st[p] - st[i]))
            return false;

    return true;
}

void bk(int p)
{
    for(int i = 1; i <= N; i++)
        if(!d[i])
        {
            st[p] = i;

            d[i] = 1;

            if(Check_Diagonals(p))
                if(p != N)
                    bk(p + 1);
                else
                    Push_Sol();

            d[i] = 0;
        }
}

int main()
{
    fin >> N;

    bk(1);

    fout << nrSol << '\n';

    return 0;
}