#include <fstream>
#include <vector>
#include <set>
using namespace std;

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

int n, k;
vector<int> sol;
set<int> usedCol, usedDiag1, usedDiag2;
int cntSol = 0;

int diagonal1(int x, int y, int n)
{
    return x + y + 1;
}

int diagonal2(int x, int y, int n)
{
    return x + n - y;
}

void queens(int r)
{
    if (r == n)
    {
        if (cntSol == 0)
        {
            for (int it : sol)
            {
                fout << it + 1 << " ";
            }
            fout << "\n";
        }
        ++cntSol;
        return;
    }
    for (int c = 0; c < n; ++c)
    {
        bool isColValid = usedCol.find(c) == usedCol.end();
        if (!isColValid)
        {
            continue;
        }
        int d1 = diagonal1(r, c, n);
        bool isDiagonal1Valid = usedDiag1.find(d1) == usedDiag1.end();
        if (!isDiagonal1Valid)
        {
            continue;
        }
        int d2 = diagonal2(r, c, n);
        bool isDiagonal2Valid = usedDiag2.find(d2) == usedDiag2.end();
        if (!isDiagonal2Valid)
        {
            continue;
        }
        usedCol.insert(c);
        usedDiag1.insert(d1);
        usedDiag2.insert(d2);
        sol.push_back(c);
        queens(r + 1);
        usedCol.erase(c);
        usedDiag1.erase(d1);
        usedDiag2.erase(d2);
        sol.pop_back();
    }
}

int main()
{
    fin >> n;
    queens(0);
    fout << cntSol;
    return 0;
}