#include<bits/stdc++.h>
using namespace std;
int n,ans[100],zx[15],yx[25],l[100],sum=0,num=0;
void dfs(int k){
	if(k==n+1){
		sum++;
		if(sum<=3){
			for(int i=1;i<=n;i++){
					cout<<ans[i]<<" ";	
			}
		cout<<endl;
		}
	
	}else{
		for(int j=1;j<=n;j++){
			if(l[j]==1||yx[j+k]==1||zx[n+k-j]==1||ans[k]==j){
				continue;
			}
			ans[k]=j;
			l[j]=1;
			yx[j+k]=1;
			zx[n+k-j]=1;
			dfs(k+1);
			ans[k]=0;
			l[j]=0;
			yx[j+k]=0;
			zx[n+k-j]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<sum;
	return 0;
}