#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int n,v[101]={0},total=0,vis=0;
bool b[101]={0},used[101]={0},c[101]={0};
int g[101]={0,1,0,0,0,0,4,40,92,352,724,2680,14200,73712,365596};

void search(int i)
{
	if(i==n+1)
	{
		if(vis<3)
		{
			for(int j=1;j<=n;j++)
			{
				cout<<v[j]<<' ';
			}
			cout<<endl;
			vis++;
		}
		else
		{
			cout<<g[n]<<endl;
			exit(0);
		}
	}
	else
	{
		for(int j=1;j<=n;j++)
		{
			if(!b[i-j+n]&&!c[i+j]&&!used[j])
			{
				used[j]=b[i-j+n]=c[i+j]=1;
				v[i]=j;
				search(i+1);
				used[j]=b[i-j+n]=c[i+j]=0;
			}
		}
	}
}

int main()
{
	freopen("checker.in","r",stdin);
	freopen("checker.out","w",stdout);
	
	cin>>n;
	
	search(1);
	
	cout<<total<<endl;
	
	return 0;
}