#include <fstream>
#include <cstring>

#define Nmax 30

using namespace std;

int N, Solutions, A[Nmax], firstSolution[Nmax];
bool Line[Nmax], mainDiagonal[Nmax], secondDiagonal[Nmax];

void Back(int column) {

    for(int row = 1; row <= N; row++)
        if(!Line[row] && !mainDiagonal[row + column] && !secondDiagonal[N + row - column]) {

            A[column] = row;
            Line[row] = true;
            mainDiagonal[row + column] = true;
            secondDiagonal[N + row - column] = true;

            if(column == N) {
                ++Solutions;
                if(firstSolution[1] == 0)
                    memcpy(firstSolution, A, sizeof(A));
            } else
                Back(column + 1);

            Line[row] = false;
            mainDiagonal[row + column] = false;
            secondDiagonal[N + row - column] = false;

            }

}
void Read() {

    ifstream in("damesah.in");
    in >> N;
    in.close();

}
void Write() {

    ofstream out("damesah.out");

    for(int i = 1; i <= N; i++)
        out << firstSolution[i] << ' ';

    out << '\n' << Solutions << '\n';
    out.close();

}
int main() {

    Read();
    Back(1);
    Write();

    return 0;

}