#include <fstream>
std::ifstream cin("damesah.in");
std::ofstream cout("damesah.out");
#define maxn 14

int v[maxn],row[maxn],diagPrin[maxn*2],diagSec[maxn*2];
int n,nrsol;

bool valid(int x,int y,int z){
	return (!row[x]&&!diagSec[y]&&!diagPrin[z]);
}

void bkt(){
	int k=1;
	while(k>0){
		int eSol=0;
		while(v[k]<n&&!eSol){
			v[k]++;
			eSol=valid(v[k],k+v[k],n-v[k]+k-1);
		}
		if(!eSol){
			k--;
			row[v[k]]=diagSec[k+v[k]]=diagPrin[n-v[k]+k-1]=0;
			continue;
		}
		if(k==n){
			if(!nrsol)
				for(int i=1;i<=n;i++)
					cout<<v[i]<<' ';
			nrsol++;
			--k;
		}else{
			row[v[k]]=diagSec[k+v[k]]=diagPrin[n-v[k]+k-1]=1;
			v[++k]=0;
		}
	}
}

int main()
{
	cin>>n;
	bkt();
	cout<<'\n'<<nrsol;
}