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

int v[maxn];
int n,nrsol;

int solutie(int k){
	if(k==n){
		if(!nrsol)
			for(int i=1;i<=n;i++)
				cout<<v[i]<<' ';
		return 1;
	}
	return 0;
}

int valid(int k){
	for(int i=1;i<k;i++)
		if(v[i]==v[k]||(k-i)==abs(v[k]-v[i]))
			return 0;
	return 1;
}

void bkt(int k){
	for(int i=1;i<=n;i++){
		v[k]=i;
		if(valid(k)){
			if(solutie(k))
				++nrsol;
			else
				bkt(k+1);
		}
	}
}

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