#include <cstdio>
#define Nmax 14
using namespace std;

FILE *fi = fopen("damesah.in", "r");
FILE *fo = fopen("damesah.out", "w");

int n;
int poz[Nmax];
char dp[Nmax*2];
char ds[Nmax*2];
char c[Nmax];
long long ct;
int sem = 1;

void afisare()
{
	sem = 0;
	for (int i = 1; i<=n; i++)
		fprintf(fo, "%d ", poz[i]);
}

void bt(int k)
{
	if (k == n+1)
	{
		ct++;
		if (sem) afisare();
	}
	
	for (int i = 1; i<=n; ++i)
		if (!c[i] && !dp[i - k + n] && !ds[i + k])
		{
			poz[k] = i;
			c[i] = 1;
			dp[i-k+n] = 1;
			ds[i+k] = 1;
			
			//if (k < n)
				bt(k+1);
			
			c[i] = 0;
			dp[i-k+n] = 0;
			ds[i+k] = 0;
		}
}

int main()
{
	fscanf(fi, "%d", &n);
	bt(1);
	fprintf(fo, "\n%lld", ct);
	return 0;
}