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

int di[2] = { 1,1};
int dj[2] = {-1,1};

int a[30][30];

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 && a[k][i] == 0) {
			x[k]=i;
			f[i] = 1;
			
			for (int d=0;d<=1;d++) {
				int ii = k+di[d];
				int jj = i+dj[d];
				while (ii<=n && jj>=1 && jj<=n) {
					a[ii][jj] ++;
					ii+=di[d];
					jj+=dj[d];
				}
			}
			
			rec(k+1);
			
			for (int d=0;d<=1;d++) {
				int ii = k+di[d];
				int jj = i+dj[d];
				while (ii<=n && jj>=1 && jj<=n) {
					a[ii][jj] --;
					ii+=di[d];
					jj+=dj[d];
				}
			}
			
			f[i] = 0;
		}
	}
}

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