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

using namespace std;

int n;
int total_solutions = 0;
vector<int> sol;
vector<int> first_sol;
bool first_found = false;

vector<bool> col_used;
vector<bool> diag1;
vector<bool> diag2;

void bkt(int r) {
    if (r > n) {
        total_solutions++;
        
        if (!first_found) {
            first_found = true;
            first_sol = sol;
        }
        return;
    }

    for (int c = 1; c <= n; ++c) {
        if (!col_used[c] && !diag1[r - c + n] && !diag2[r + c]) {
            col_used[c] = true;
            diag1[r - c + n] = true;
            diag2[r + c] = true;
            sol[r] = c;
            bkt(r + 1);
            col_used[c] = false;
            diag1[r - c + n] = false;
            diag2[r + c] = false;
        }
    }
}

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

    fin >> n;

    sol.assign(n + 1, 0);
    col_used.assign(n + 1, false);
    diag1.assign(2 * n + 1, false);
    diag2.assign(2 * n + 1, false);

    bkt(1);

    for (int i = 1; i <= n; ++i)
        fout << first_sol[i] << (i == n ? "\n" : " ");

    fout << total_solutions << "\n";

    return 0;
}