#include<stdio.h>
#include<math.h>

int pozitionat[30], solutie[30];

int validare( int k)
{
	int i;
	for(i=1; i<=k-1; i++)
		if( (pozitionat[k] == pozitionat[i]) || (abs(pozitionat[k] - pozitionat[i]) == abs(k - i))) 
			{
				return 0; //nu e ok - se pot ataca
		    }
	
	return 1; //e ok - nu se ataca
}

void afisare(int n)
{
	int i;
	for(i=1; i<=n; i++)
	{
		solutie[i] = pozitionat[i];
	}
}

int bck(int n)
{
	int nrSolutii = 0;
	int k, amSolutie;
	int primaSolutie = 1;

	k=1;
	pozitionat[k]=0;
	while(k > 0)
	{
		amSolutie=0;
		while( (pozitionat[k] < n) && (!amSolutie))
		{
			pozitionat[k]++;
			amSolutie = validare(k);
		}
		if(!amSolutie)
		{
			k--;
		}
		else
		{
			if( k==n )
			{
				if(primaSolutie == 1)
				{
					afisare(n);
					primaSolutie=0;
				}
				nrSolutii++;
			}
				else
				{
					k++;
				    pozitionat[k]=0;
			}
	}
}
	return nrSolutii;
}





int main()
{
	FILE *inputFile, *outputFile;
	inputFile=fopen("damesah.in", "r");
	outputFile=fopen("damesah.out", "w");

	int n, nrSolutii;
	fscanf(inputFile, "%d", &n);
	nrSolutii=bck(n);
	for(int i=1; i<=n; i++)
	{
		fprintf(outputFile,"%d ", solutie[i]);
     }
	fprintf(outputFile,"\n");
	fprintf(outputFile, "%d", nrSolutii);
	return 0;
}