#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("damesah.in");
ofstream cout ("damesah.out");

void backt(int currentLine, const int queens, int &totalNumber,
           vector <bool> &columns, vector <bool> &mainDiagonal,
           vector <bool> &secDiagonal, vector <int> &partialSolution) {
    static bool displayed = false;
    if (currentLine == queens + 1)
    {
        totalNumber += 1;
        if (!displayed) {
            displayed = true;
            for (auto &line : partialSolution) {
                cout << line << ' ';
            }
            cout << '\n';
        }
    }
    else
    {
        for (int possibleColumn = 1; possibleColumn <= queens; ++ possibleColumn)
        {
            if (columns[possibleColumn] or
                mainDiagonal[currentLine - possibleColumn + queens] or
                secDiagonal[currentLine + possibleColumn])
                continue;
            columns[possibleColumn] = true;
            mainDiagonal[currentLine - possibleColumn + queens] = true;
            secDiagonal[currentLine + possibleColumn] = true;
            partialSolution.push_back(possibleColumn);
            backt(currentLine + 1, queens, totalNumber, columns, mainDiagonal, secDiagonal, partialSolution);
            partialSolution.pop_back();
            columns[possibleColumn] = false;
            mainDiagonal[currentLine - possibleColumn + queens] = false;
            secDiagonal[currentLine + possibleColumn] = false;
        }
    }
}

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int queens;
    cin >> queens;
    int answer = 0;
    vector <bool> columns(static_cast<unsigned int>(queens + 1), false);
    vector <bool> mainDiagonal(static_cast<unsigned int>(2 * queens + 1), false);
    vector <bool> secDiagonal(static_cast<unsigned int>(2 * queens + 1), false);
    vector <int> partialSolution;
    backt(1, queens, answer, columns, mainDiagonal, secDiagonal, partialSolution);
    cout << answer << '\n';
    return 0;
}