#include <iostream>
#define _for(i,where,to) for(int i = (where); i <= (to); i++)
using namespace std;

int cols[13];
int cnt = 0;

int readInt() {
	int tmp;
	cin >> tmp;
	return tmp;
}

bool tryPlace(int gridLen, int y, int x) {
	_for(i, 0, y - 1)
		if (cols[i] == x)
			return false;
		else if (cols[i] < x && cols[i] - i == x - y)
			return false;
		else if (cols[i] > x && cols[i] + i == x + y)
			return false;
	return true;
}

void whenFound(int gridLen) {
	cnt++;
	if (cnt > 3)
		return;
	_for(i, 0, gridLen - 1)
		printf("%d ", cols[i] + 1);
	printf("\n");
	return;
}

void solve(int gridLen, int y) {
	if (y == gridLen) {
		whenFound(gridLen);
		return;
	}
	_for(x, 0, gridLen - 1) {
		if (tryPlace(gridLen, y, x)) {
			cols[y] = x;
			solve(gridLen, y + 1);
		}
	}
}

int main() {
	solve(readInt(), 0);
	printf("%d", cnt);
	return 0;
}