#include <fstream>


using namespace std;

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

bool initialMap[15][15];
int solutions;
int firstSolution[14];
int n;

void fillLine(int line, int size, bool map[15][15]) {
    for (int i = 1; i <= size; i++) {
        map[line][i] = true;
    }
}

void fillCollumn(int collumn, int size, bool map[15][15]) {
    for (int i = 1; i <= size; i++) {
        map[i][collumn] = true;
    }
}

void fillDiagonals(int line, int collumn, int size, bool map[15][15]) {

    map[line][collumn] = true;

    for (int i = line + 1, j = collumn + 1; i <= size && j <= size; i++, j++) {
        map[i][j] = true;
    }
    for (int i = line - 1, j = collumn - 1; i > 0 && j > 0; i--, j--) {
        map[i][j] = true;
    }

    for (int i = line - 1, j = collumn + 1; i > 0 && j <= size; i--, j++) {
        map[i][j] = true;
    }
    for (int i = line + 1, j = collumn - 1; i <= size && j > 0; i++, j--) {
        map[i][j] = true;
    }

}

void place(int line, int collumn, int size, bool map[15][15]) {
    fillLine(line, size, map);
    fillCollumn(collumn, size, map);
    fillDiagonals(line, collumn, size, map);
}

void solve(int line, int size, bool map[15][15]) {
    bool newMap[15][15];
    for (int i = 1; i <= n; i++) {
        if (!map[line][i]) {
            if (solutions == 0)
                firstSolution[line] = i;

            if (line < size)
            {
                for (int i = 1; i <= size; i++) {
                    for (int j = 1; j <= size; j++) {
                        newMap[i][j] = map[i][j];
                    }
                }

                place(line, i, size, newMap);
                solve(line + 1, size, newMap);
            }
            else {
                solutions++;
            }
        }
    }
}

int main()
{
    fin >> n;
    solve(1, n, initialMap);
    for (int i = 1; i <= n; i++) {
        fout << firstSolution[i] << " ";
    }
    fout << "\n" << solutions;
}