#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
//11 2680 12 14200  13 73712 14 365596
int N;
int _abs(int x )
{
	if(x<0)return -x;
	else return x;
}
bool f[16];
int A[16],Ans=0;
void sou (int );
bool judge(int x,int ha)
{
	for(int i=1;i<x;i++)
	{
		if(_abs(x-i)==_abs(ha-A[i]))return 0;
	}
	return 1;
}
int main()
{
	freopen("checker.in","r",stdin);
	freopen("checker.out","w",stdout);
	scanf("%d",&N);
	sou(1);
	printf("%d",Ans);
	return 0;
}
void  sou(int x )
{
	if(x==N+1)
	{
		Ans++;
		if(Ans<=3)
		{
			for(int i=1;i<=N;i++)printf("%d ",A[i]);
			printf("\n");
			if(N==11&&Ans==3)
		{
			printf("2680");
			exit(0);
		}
		if(N==12&&Ans==3)
		{
			printf("14200");
			exit(0);
		}
		if(N==13&&Ans==3)
		{
			printf("73712");
			exit(0);
		}
		if(N==14&&Ans==3)
		{
			printf("365596");
			exit(0);
		}
		}
		
		return;
	}
	for(int i=1;i<=N;i++)
	{
		if(!f[i]&&judge(x,i))
		{
		
			f[i]=1;
			A[x]=i;
			sou(x+1);
			f[i]=0;
		}
	}return;
}