#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<vector<int>> solutions;
vector<int> board;
vector<bool> column, diag1, diag2;

void backtrack(int row) {
    if (row == N) {
        solutions.push_back(board);
        return;
    }

    for (int col = 0; col < N; ++col) {
        if (column[col] || diag1[row + col] || diag2[row - col + N - 1]) continue;

        board[row] = col + 1;
        column[col] = diag1[row + col] = diag2[row - col + N - 1] = true;

        backtrack(row + 1);

        column[col] = diag1[row + col] = diag2[row - col + N - 1] = false;
    }
}

int main() {
    ifstream infile("damesah.in");
    ofstream outfile("damesah.out");

    infile >> N;

    board.resize(N);
    column.resize(N, false);
    diag1.resize(2 * N - 1, false);
    diag2.resize(2 * N - 1, false);

    backtrack(0);

    sort(solutions.begin(), solutions.end());

    if (!solutions.empty()) {
        for (int i = 0; i < N; ++i) {
            outfile << solutions[0][i] << " ";
        }
        outfile << endl;
    }

    outfile << solutions.size() << endl;

    infile.close();
    outfile.close();

    return 0;
}