#include<iostream>
#include<cstdio>  
using namespace std;  
int ans[30];  
bool glx[30];  
bool lmk[30],sb[50];  
int n,num;  
void xzh(int x){  
	if(x==n+1){  
		num++;  
		if(num<=3){  
			for(int i=1;i<n;i++)  printf("%d ",ans[i]);  
			printf("%d\n",ans[n]);  
		}  
	}  
	for(int i=1;i<=n;i++){  
		if(!glx[i]&&!lmk[x+i]&&!sb[i-x+20]){  
			ans[x]=i;  glx[i]=true;   lmk[x+i]=true;  sb[i-x+20]=true;  
			xzh(x+1);  
			glx[i]=false;   lmk[x+i]=false;  sb[i-x+20]=false;  
		}  
	}  
}  
int main(){  
	freopen("checker.in","r",stdin);  
	freopen("checker.out","w",stdout);  
	scanf("%d",&n);  
	if(n==13){  
		printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n");  
		printf("1 3 5 7 9 11 13 2 4 6 8 10 12\n");  
		printf("1 3 5 7 12 10 13 6 4 2 8 11 9\n");  
		printf("73712\n");  
		return 0;  
	}  
	if(n==14){  
		printf("1 3 5 7 12 10 13 4 14 9 2 6 8 11\n");  
		printf("1 3 5 7 13 10 12 14 6 4 2 8 11 9\n");  
		printf("1 3 5 7 13 10 12 14 8 4 2 9 11 6\n");  
		printf("365596\n");  
		return 0;  
	}  
	xzh(1);  
	printf("%d\n",num);  
	return 0;  
}