#include<fstream>
#include<cstring>
using namespace std;

int N;
int st[15],sol[15],nr;
bool c[15],d1[30],d2[30];

void back(int k){
	
	if(k>N)
	{
		if(!nr)
		{
			memcpy(sol,st,sizeof(st));
		}
		++nr;
		return;
	}
	
	for(int i=1;i<=N;++i)
	  if(!c[i] && !d1[k-i+N] && !d2[k+i])
	  {
	  	st[k] = i;
	  	c[i] = d1[k-i+N] = d2[k+i] = 1;
		back(k+1);
		c[i] = d1[k-i+N] = d2[k+i] = 0;	  	
	  }	
}


int main(){
	ifstream cin("damesah.in");
	ofstream cout("damesah.out");
	
	cin>>N;
	back(1);
	for(int i = 1;i<=N;++i) cout<<sol[i]<<' ';
	cout<<'\n'<<nr<<'\n';
	
	return 0;
}