#include <fstream>
#include <bitset>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

const int maxn = 20;

bitset <maxn * 4> dp, ds, used;
int n, st[maxn], goodconf;

inline void back(int k) {
	if(k == n + 1) {
		++ goodconf;
		if(goodconf == 1)
			for(int i = 1 ; i <= n ; ++ i)
				fout << st[i] << ' ';
		return ;
	}
	for(int i = 1 ; i <= n ; ++ i)
		if(!used[i] && !dp[k + i] && !ds[n - k + i]) {
			used[i] = 1;
			dp[k + i] = 1;
			ds[n - k + i] = 1;
			st[k] = i;
			back(k + 1);
			used[i] = 0;
			dp[k + i] = 0;
			ds[n - k + i] = 0;
		}
}

int main() {
	fin >> n;
	back(1);
	fout << '\n' <<  goodconf << '\n';
}