#include <iostream>

using namespace std;

int count = 0;//解的个数
int r[100], c[100], z[100], f[100]; //分别标记行、列、主对角线、副对角线
//重要结论：a[i][j]在i-j主对角线上，在i+j副对角线上
int n;


void dfs(int i) {
	if (i > n) {
		//输出
		if (count < 2) {
			for (int j = 1; j <= n; j++)
				cout << r[j] << " ";
			cout << endl;
		}

		count++;
		return;
	}
	//遍历每一列的可能性
	for (int j = 1; j <= n; j++) {
		if (c[j] == 0 && z[i - j + n] == 0 && f[i + j] == 0) {
			cout << z[i - j + n];
			z[i - j + n] == 1;
			f[i + j] == 1;
			r[i] = j;
			c[j] = 1;
			dfs(i + 1);
			r[i] = 0;
			c[j] = 0;
			z[i - j + n] == 0;
			f[i + j] == 0;
		}
	}
}

int main() {
	cin >> n;
	dfs(1);
	cout << count << endl;

	return 0;
}