#include<fstream>
#define NMAX 15

using namespace std;

int s[NMAX], k, n, rs, D1[2*NMAX], D2[2*NMAX], L[NMAX], C[NMAX];

ifstream cin("damesah.in"); ofstream cout("damesah.out");

void BT(int k) {
	if (k>n) {
		if (!rs) {
			for (int i=1; i<=n; i++) cout<<s[i]<<" "; 
			cout<<'\n'; 
		} rs++; return;
	}
	
	for (int i=1; i<=n; i++) {
		if (!(C[i] || D1[k-i+n] || D2[k+i])) {
			C[i] = D1[k-i+n] = D2[k+i] = 1;
			s[k] = i;
			BT(k+1);
			C[i] = D1[k-i+n] = D2[k+i] = 0;
		}
	}
	
}

int main() {
	cin>>n;
	
	BT(1);
	cout<<rs;
	return 0;
}