#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define mod 15

using namespace std;

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

int n, sol[20];
long long nr;
bool col[40], L[40], R[40], flag;

void back(int lvl){
	if(lvl > n){
		if(!flag){
			flag = 1;
			for(int i = 1; i <= n; i++)
				out << sol[i] << ' ';
			out << '\n';
		}
		nr++;
		return;
	}
	for(int i = 1; i <= n; i++)
		if(!col[i] && !L[lvl - i + mod] && !R[lvl - n + i - 1 + mod]){
			col[i] = 1;
			L[lvl - i + mod] = 1;
			R[lvl - n + i - 1 + mod] = 1;
			sol[lvl] = i;
			back(lvl + 1);
			col[i] = 0;
			L[lvl - i + mod] = 0;
			R[lvl - n + i - 1 + mod] = 0;
		}
}

int main(){
	in >> n;
	back(1);
	out << nr;
	return 0;
}