#pragma GCC optimize("03")
#include <bits/stdc++.h>
using namespace std;
ifstream in ("damesah.in");
ofstream out ("damesah.out");
int n, a[25], ans;
bool c[25], d1[25], d2[25];

void backtr(int q){
	if (q == n){
		if (!ans){
			for (int i=1; i<n; i++) out << a[i] << " ";
			out << a[n];
		}
		ans++;
		return;
	}
	for (int col = 1; col <= n; col++){
		if (c[col] || d1[n-q-1+col] || d2[q+col]) continue;
  		c[col] = d1[n-q-1+col] = d2[q+col] = 1;
  		a[q+1] = col;
		backtr(q+1);
		c[col] = d1[n-q-1+col] = d2[q+col] = 0;
	}
}

int main(){
	in >> n;
	backtr(0);
	out << "\n" << ans;
	return 0;
}