#include <bits/stdc++.h>

using namespace std;

int length;
int answers;

bool printed;

vector <bool> lines;
vector <bool> columns;
vector <bool> mainDiagonals;
vector <bool> secondaryDiagonals;

vector <int> coordonates;

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

template <typename Type>
inline void resizeVector(vector<Type> &argument, int length){
    for (int index = 0; index < length; index++)
        argument.push_back(0);
}

inline void initialize(){
    fin >> length;

    resizeVector(lines, length);
    resizeVector(columns, length);
    resizeVector(mainDiagonals, 2*length-1);
    resizeVector(secondaryDiagonals, 2*length-1);
    resizeVector(coordonates, length);
}

bool isValid(int line, int column){

    if (columns[column])
        return false;

    if (mainDiagonals[line-column+length-1])
        return false;

    if (secondaryDiagonals[line+column])
        return false;

    return true;
}

void generateSolutions(int line = 0, int placed = 0){
    if (line == length){
        if (placed == length){
            if (not printed){
                for (auto it : coordonates)
                    fout << it+1 << " ";
                printed = true;
            }
            answers++;
        }
        return;
    }

    for (int column = 0; column < length; column++){

        if (isValid(line, column)){
            if (not printed)
                coordonates[line] = column;

            columns[column] = true;
            mainDiagonals[line-column+length-1] = true;
            secondaryDiagonals[line+column] = true;

            generateSolutions(line+1, placed+1);

            columns[column] = false;
            mainDiagonals[line-column+length-1] = false;
            secondaryDiagonals[line+column] = false;
        }
    }
}

int main(){
    initialize();
    generateSolutions();
    fout << "\n" << answers;
}