#include<fstream>

using namespace std;

int s[15], k, n, rs;

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

bool check(int j, int k) {
	for (int i=1; i<k; i++) {
		if (s[i]==j || k-i==abs(j-s[i])) return 0;
	}
	return 1;
}

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 (check(i,k)) {
			s[k]=i;
			BT(k+1);
		}
	}
	
}

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