#include<bits/stdc++.h>

using namespace std;

ofstream fout("damesah.out");

int n,k2;
int a[30][30];
int MC[50],MD1[50],MD2[50];
bool v;
bool OK(int i, int j) {
/*	int i2=i, j2=j;
	while (i>=1 && j>=1 && j<=n && i<=n) {
		if (a[i][j]==1) {
			u=1; break;
		}
		i--;
		j--;
		
	}
	if (u) return 0;

	i=i2,j=j2;
	while (i>=1 && j>=1 && j<=n && i<=n) {
		if (a[i][j]==1) {
			u=1; break;
		}
		i--;
		j++;
	}
	if (u) return 0;
	i=i2,j=j2;
	while (i>=1 && j>=1 && j<=n && i<=n) {
		if (a[i][j]==1) {
			u=1; break;
		}
		i--;
	}*/
	if (MC[j]==1 || MD1[i+j]==1 || i-j>=0 && MD2[i-j]==1 || i-j<0 && MD2[i-j+30]==1) return 0;
	return 1;
}

void BT(int k) {
	if (k==n+1) {
		k2++;
		if (k2==1) {
			for (int i=1; i<=n; i++) {
				for (int j=1; j<=n; j++) if (a[i][j]==1) fout<<j<<" ";
			} fout<<endl;
		}
		
		 return;
	}
	for (int j=1; j<=n; j++) {
		if (OK(k,j)) {
			MC[j]=1;
			MD1[k+j]=1;
			if (k-j<0) MD2[k-j+30]=1;
			else MD2[k-j]=1;
			a[k][j]=1;
			BT(k+1);
			a[k][j]=0;
			MC[j]=0;
			MD1[k+j]=0;
			if (k-j<0) MD2[k-j+30]=0;
			else MD2[k-j]=0;
		}
		
	}
	
	
}


int main() {
	//ifstream cin("damesah.in");
	cin>>n;
	
	BT(1);
	fout<<k2;
	
}