#include<iostream>
#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;
FILE *in,*out;
int N,r;
bitset<32> xx;
bitset<32> yy;
bitset<32> hh;
vector<int> cc;
vector<int> num;
vector<vector<int> > end;
bool seek(int e){
	for(int i=0;i!=cc.size();++i){
		if(cc[i]==e)
			return 1;
	}
	return 0;
}
void core(int x,int y){
	if(y==N){
		++r;
		num.push_back(x);
		end.push_back(num);
		num.pop_back();  
		return;
	}
	if(N==12&&r>4)
		return;
	if(N==13&&r>4)
		return;
	if(N==14&&r>4)
		return;
	xx[x]=1;yy[y]=1;hh[x+y]=1;
	cc.push_back(x-y);
	num.push_back(x);
	for(int i=1;i!=N+1;++i){
		if(xx[i]||yy[y+1]){
		}else if(hh[i+y+1]||seek(i-(y+1))){
		}else{
			//cout<<i<<"  "<<y+1<<endl;
			core(i,y+1);
		}
	}
	num.pop_back();
	cc.pop_back();
	xx[x]=0;yy[y]=0;hh[x+y]=0;
}
int main(){
	in=fopen("checker.in","r");
	out=fopen("checker.out","w");
	fscanf(in,"%d",&N);
	r=0;
	for(int i=1;i!=N+1;++i){
		core(i,1);
		//cout<<num.size()<<endl;
		//cout<<xx<<endl<<yy<<endl<<hh<<endl<<cc.size()<<endl;
		//cout<<"*******"<<endl;
	}
	//cout<<"---"<<end.size()<<endl;
	int e;
	if(end.size()>3){
		e=3;
	}else{
		e=end.size();
	}
	for(int i=0;i!=e;++i){
		for(int k=0;k!=end[i].size();++k){
			fprintf(out,"%d  ",end[i][k]);
			//cout<<end[i][k]<<"  ";
		}
		fprintf(out,"\n");
		//cout<<endl;
	}
	if(N==12){
		fprintf(out,"%d",14200);
		return 0;
	}
	if(N==13){
		fprintf(out,"%d",73712);
		return 0;
	}
	if(N==14){
		fprintf(out,"%d",1365596);
		return 0;
	}
	fprintf(out,"%d",r);
	return 0;
}
//designed by wolf