#include<fstream>
using namespace std;
int i, j, x[23], f[23], nrsol, n;
FILE*fin=fopen("damesah.in","r");
ofstream fout("damesah.out");

inline int modul(int x){
	return (x<0    ?   -x   :    x);
}
int cont(int k){
	for(int i=1; i<k; i++)
		if(modul(i-k)==modul(x[i]-x[k]))
			return 0;
		return 1;
}

int rec(int k){
	if(k==n+1){
		nrsol++;
		if(nrsol==1){
			for(j=1; j<=n; j++)
				fout<<x[j]<<" ";
			fout<<"\n";
		}
		
	}
	for(int i=1; i<=n; i++){
		if (f[i] == 0) {
			x[k]=i;
			f[i] = 1;
			if(cont(k))
				rec(k+1);
			f[i] = 0;
		}
	}
}

int main(){
	fscanf(fin,"%d", &n);
	rec(1);
	fout<<nrsol;
return 0;
}