#include <bits/stdc++.h>

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int ans=0,anss[21];
int n;
bool coloana[21],diagpr[41],diagsec[41];
void solve(int pos)
{
	if(pos==n+1)
	{
		ans++;
		if(ans==1)
		{
			for(int i=1;i<=n;i++)
				out<<anss[i]<<" ";
			out<<"\n";
		}
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(coloana[i]==0 && diagpr[pos-i+n]==0 && diagsec[pos+i]==0)
		{
			coloana[i]=1;
			diagpr[pos-i+n]=1;
			diagsec[pos+i]=1;
			anss[pos]=i;
			solve(pos+1);
			coloana[i]=0;
			diagpr[pos-i+n]=0;
			diagsec[pos+i]=0;
		}
	}
}
int main()
{
	in>>n;
	solve(1);
	out<<ans;
	return 0;
}