#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;

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 (!(MC[j]==1 || MD1[k+j]==1 ||  MD2[k-j+n+1]==1)) {
			MC[j]=1;
			MD1[k+j]=1;
			MD2[k-j+n+1]=1;
			a[k][j]=1;
			BT(k+1);
			a[k][j]=0;
			MC[j]=0;
			MD1[k+j]=0;
			MD2[k-j+n+1]=0;
		}
		
	}
	
	
}


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