#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;

int rez[30], rs, n;
bool diag[3][30], col[15];
vector < vector < int > > V(1000000);

int getDiag1(int x, int y) {
	return n - x + y;
}

int getDiag2(int x, int y) {
	return x + y - 1;
}

void back(int x, int lin) {
	if (x == n + 1) {
		for (int i = 1; i <= n; i++) V[rs].push_back(rez[i]);
		rs++;
		return ;
	}

	for (int i = 1; i <= n; i++) {
		int diag1 = getDiag1(lin, i);
		int diag2 = getDiag2(lin, i);

		if (col[i] || diag[1][diag1] || diag[2][diag2])
			continue;

		rez[x] = i;
		col[i] = diag[1][diag1] = diag[2][diag2] = 1;
		back(x + 1, lin + 1);
		col[i] = diag[1][diag1] = diag[2][diag2] = 0;
		rez[x] = 0;
	}
}

int main(){
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

	cin >> n;
	back(1, 1);

	// sort(V.begin(), V.end());
	for (auto it : V[0]) cout << it << " ";

	cout << "\n" << rs;
	return 0;
}