#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
using namespace std;
const string IN_FILE = "damesah.in";
const string OUT_FILE = "damesah.out";
class Solver {
public:
Solver(const int _n) :
n(_n),
queens(vector<int>()),
columns(vector<bool>(n)),
diagonals(vector<bool>(2 * n - 1)),
secondaryDiagonals(vector<bool>(2 * n - 1)),
first(vector<int>()),
count(0) {}
pair<vector<int>, int> solve() {
if (first.empty()) {
back();
}
return make_pair(first, count);
}
private:
int n;
vector<int> queens;
vector<bool> columns, diagonals, secondaryDiagonals;
vector<int> first;
int count;
void back() {
const int r = int(queens.size());
if (r == n) {
if (first.empty()) {
first = queens;
}
count++;
return;
}
for (int c = 0; c < n; c++) {
const int d = r - c + (n - 1);
const int sd = r + c;
if (columns[c] || diagonals[d] || secondaryDiagonals[sd]) continue;
queens.push_back(c);
columns[c] = true;
diagonals[d] = true;
secondaryDiagonals[sd] = true;
back();
queens.pop_back();
columns[c] = false;
diagonals[d] = false;
secondaryDiagonals[sd] = false;
}
}
};
int readInput() {
ifstream in(IN_FILE);
int n;
in >> n;
in.close();
return n;
}
void writeOutput(const vector<int>& first, const int count) {
ofstream out(OUT_FILE);
for (int i = 0; i < int(first.size()); i++) {
out << first[i] + 1 << (i + 1 < int(first.size()) ? " " : "\n");
}
out << count << "\n";
out.close();
}
int main() {
const int n = readInput();
vector<int> first;
int count;
tie(first, count) = Solver(n).solve();
writeOutput(first, count);
return 0;
}