#include<fstream>
using namespace std;
int i, j, x[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(x[i]==x[k] || 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++){
		x[k]=i;
		if(cont(k))
			rec(k+1);
	}
}

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