#include<fstream>
#include<math.h>
using namespace std;

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

int N, x[100];
bool b, q=1 ;
int k=1, sol;
bool check(int q)
{
	for(int i=1; i<q; i++) 
	if((x[q]==x[i])||(q-i==abs(x[q]-x[i]))) return 0;
	return 1;
}

void BackTrakingIterativ(int N)
{
	//fo << " check\n";
	
	while(k>0)
	{
		b=0;
		while((x[k]<N) && !b) x[k]++, b = check(k);
		if(!b)k--;
		else 
		{
			
			if(k==N)
			{
				if(q) 
				{
					for(int i=1; i<=N; i++) fo << x[i] << " ";
					fo << '\n';
					q=0;
				}
				sol++;
			}
			else k++, x[k]=0;	
		}
	}
	fo << sol;
}


int main()
{
	fi >> N;
	BackTrakingIterativ(N);
	
}