#include <fstream>

using namespace std;

inline int getIndexDiag1(int line, int col, int N)
{
    return line - col + (N - 1);
}

inline int getIndexDiag2(int line, int col)
{
    return line + col - 2;
}

void perm(int line, int config[],
          bool onCol[], bool onDiag1[], bool onDiag2[],
          const int &N, int &result, ofstream &g)
{
    if (line == N + 1)
    {
        result++;
        if (result == 1)
        {
            for (int i = 1; i <= N; i++)
                g << config[i] << ' ';
            g << '\n';
        }
    }
    else
        for (int col = 1; col <= N; col++)
        {
            int d1 = getIndexDiag1(line, col, N);
            int d2 = getIndexDiag2(line, col);
            if (!onCol[col] && !onDiag1[d1] && !onDiag2[d2])
            {
                onCol[col] = onDiag1[d1] = onDiag2[d2] = true;
                config[line] = col;
                perm(line + 1, config, onCol, onDiag1, onDiag2,
                        N, result, g);
                onCol[col] = onDiag1[d1] = onDiag2[d2] = false;
            }
        }
}

int main()
{
    ifstream f("damesah.in");
    int N;
    f >> N;
    f.close();

    int diagLength = N + (N - 1);
    bool onCol[N + 1], onDiag1[diagLength], onDiag2[diagLength];
    int config[N + 1];
    fill(onCol, onCol + N + 1, false);
    for (int i = 0; i < diagLength; i++)
        onDiag1[i] = onDiag2[i] = false;

    int result = 0;
    ofstream g("damesah.out");
    perm(1, config, onCol, onDiag1, onDiag2, N, result, g);
    g << result;
    g.close();
    return 0;
}