#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

#ifdef INFOARENA
#define ProblemName "damesah"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 15
int st[MAXN];
char cols[MAXN], diags[MAXN << 1], bdiags[MAXN << 1];

inline int getDiag(int ln, int col) {
	return (ln - col) + MAXN;
}

inline int getbDiag(int ln, int col) {
	return (ln + col);
}

int bkt(int n) {
	int sols = 0;
	int k = 0;
	st[k] = -1;
	memset(cols, 0, sizeof(cols));
	memset(diags, 0, sizeof(diags));
	while (k >= 0) {
		char OK = 0;
		while (!OK && st[k] < n - 1) {
			OK = 1;
			st[k]++;
			if (cols[st[k]]) OK = 0;
			if (diags[getDiag(k, st[k])]) OK = 0;
			if (diags[getbDiag(k, st[k])]) OK = 0;
		}
		if (OK) {
			if (k == n - 1) {
				if ((sols++) == 0) {
					for (int i = 0; i <= k; i++)
						printf("%d ", st[i] + 1);
					putchar('\n');
				}
			}
			else {
				cols[st[k]] = diags[getDiag(k, st[k])] = diags[getbDiag(k, st[k])] = 1;
				k++;
				st[k] = -1;
			}
		}
		else {
			k--;
			if (k >= 0) cols[st[k]] = diags[getDiag(k, st[k])] = diags[getbDiag(k, st[k])] = 0;
		}
	}
	return sols;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	int N;
	scanf("%d", &N);
	printf("%d\n", bkt(N));
	return 0;
}