#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

int N;
int total_solutions = 0;
bool first_solution_found = false;

vector<int> sol;
vector<int> first_sol;

vector<bool> col_occupied;
vector<bool> diag1_occupied; // pentru row - col + N
vector<bool> diag2_occupied; // pentru row + col

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

void backtracking(int row) {
    // Daca am plasat cu succes toate cele N dame
    if (row == N + 1) {
        total_solutions++;
        if (!first_solution_found) {
            first_sol = sol;
            first_solution_found = true;
        }
        return;
    }

    // Incercam sa plasam dama de pe linia 'row' pe fiecare coloana 'col' de la 1 la N
    for (int col = 1; col <= N; ++col) {
        int d1 = row - col + N;
        int d2 = row + col;

        if (!col_occupied[col] && !diag1_occupied[d1] && !diag2_occupied[d2]) {
            col_occupied[col] = true;
            diag1_occupied[d1] = true;
            diag2_occupied[d2] = true;
            sol[row] = col;

            backtracking(row + 1);

            col_occupied[col] = false;
            diag1_occupied[d1] = false;
            diag2_occupied[d2] = false;
        }
    }
}

int main() {
    fin >> N;

    sol.resize(N + 1);
    col_occupied.resize(N + 1, false);
    diag1_occupied.resize(2 * N + 1, false);
    diag2_occupied.resize(2 * N + 1, false);

    backtracking(1);

    for (int i = 1; i <= N; ++i) {
        fout << first_sol[i] << " ";
    }
    fout << "\n";

    fout << total_solutions << "\n";

    return 0;
}