#include <bits/stdc++.h>
using namespace std;
bool b[100],c[100],d[100];
int ans=0,n,a[100];
void dfs(int i)
{
	
	if(i==n+1){
		for(int j=1;j<=n;j++)cout<<a[j]<<" ";
		cout<<endl;
		ans++;
		return;
	}	
	for(int j=1;j<=n;j++){
		if(b[j]==0&&c[i+j]==0&&d[i-j+n-1]==0){
			a[i]=j;
			b[j]=1;
			c[i+j]=1;
			d[i-j+n-1]=1;
			dfs(i+1);
			b[j]=0;
			c[i+j]=0;
			d[i+j-n-1]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);
	cout<<ans;
	return 0;
}