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

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

typedef vector<int> vec_i;
typedef vector<bool> vec_b;

vec_i sol;
vec_b colOcup,mainDiagOcup,secDiagOcup;
size_t n,solCount;

bool isSafe(int i, int j) {
	return !(colOcup[j]||mainDiagOcup[n+j-i]||secDiagOcup[i+j]);
}

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

void solve(size_t i) {
	if(i==n) { 
		if(solCount == 0)
			printSol();
		solCount++;
		return;
	}
	for(size_t j = 0; j < n; ++j) {
		if(isSafe(i,j)) {
			sol[i] = j;
			colOcup[j] = true;
			mainDiagOcup[n+j-i] = true;
			secDiagOcup[i+j] = true;
			solve(i+1);
			secDiagOcup[i+j] = false;
			mainDiagOcup[n+j-i] = false;
			colOcup[j] = false;
		}
	}
}

int main() {
	in >> n;
	sol.resize(n);
	colOcup.resize(n,false);
	mainDiagOcup.resize(2*n,false);
	secDiagOcup.resize(2*n,false);
	solve(0);
	out << solCount << '\n';
}