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

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");

typedef vector<int> vec_i;

vec_i sol;
size_t n,solCount;

bool isSafe(int pI, int pJ) {
	for(int i = 0; i < pI; ++i)
		if(pJ == sol[i] || pI-i == abs(pJ - sol[i])) {
			return false;
		}
	return true;
}

void printSol() {
	for(size_t i = 0; i < n; ++i)
		out << sol[i]+1 << ' ';
	out << '\n';
}

void solve(size_t lvl) {
	if(lvl==n) { 
		if(solCount == 0)
			printSol();
		solCount++;
		return;
	}
	for(size_t i = 0; i < n; ++i) {
		if(isSafe(lvl,i)) {
			sol[lvl] = i;
			solve(lvl+1);
		}
	}
}

int main() {
	in >> n;
	sol.resize(n);
	solve(0);
	out << solCount << '\n';
}