#include<iostream>
using namespace std;
int n;
int clmn[20];
int myleft[30];
int myright[30];
int res[20];
int cnt;
void pa(){
	if(cnt<=3){
		for(int i=1;i<=n;i++){
			cout<<res[i]<<' ';
		}
		cout<<endl;
	}
}
void dfs(int k){
	if(k==n+1){
		cnt++;
		pa();
		return;
	}
	for(int i=1;i<=n;i++){
		if(clmn[i]==0 && myleft[k+i]==0 && myright[k-i+n]==0){
			clmn[i]=1;
			myleft[k+i]=1;
			myright[k-i+n]=1;
			res[k]=i;
			dfs(k+1);
			clmn[i]=0;
			myleft[k+i]=0;
			myright[k-i+n]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<cnt;
	return 0;
}