#include <fstream>

class Board
{
    int size;
    bool first;
    int *pos;
    bool *col;
    bool *m;
    bool *s;
    int solve(std::ostream& out, int line)
    {
        if (line == size)
        {
            if (first)
            {
                first = false;
                for (int i = 0; i < size; i++)
                {
                    out << pos[i] + 1 << ' ';
                }
                out << '\n';
            }
            return 1;
        }
        int sum = 0;
        for (int column = 0; column < size; column++)
        {
            if (!col[column] && !s[column + line] && !m[column - line + size - 1])
            {
                col[column] = true;
                s[column + line] = true;
                m[column - line + size - 1] = true;

                pos[line] = column;
                sum += solve(out, line + 1);

                col[column] = false;
                s[column + line] = false;
                m[column - line + size - 1] = false;
            }
        }
        return sum;
    }
    void init()
    {
        for (int i = 0; i < size; i++)
        {
            pos[i] = -1;
            col[i] = false;
        }
        for (int i = 0; i < size * 2; i++)
        {
            m[i] = false;
            s[i] = false;
        }
        first = true;
    }
public:
    void solve(std::ostream& out)
    {
        init();
        out << solve(out, 0) << '\n';
    }
    Board(int nV) : size(nV), first(true), pos(new int[nV]), col(new bool[nV]),
        m(new bool[nV * 2]), s(new bool[nV * 2])
    {

    }
    ~Board()
    {
        delete[] pos;
        delete[] col;
        delete[] m;
        delete[] s;
    }
};

int main()
{
    std::ifstream in("damesah.in");
    std::ofstream out("damesah.out");
    int nV;
    in >> nV;
    in.close();
    Board myBoard = Board(nV);
    myBoard.solve(out);
    out.close();
    return 0;
}