#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>

using namespace std;

int N;

bool isValid( vector <int> table, int row, int column) {
	for (int i= 0 ; i < row; i++)
		if (column == table[i] || row - i == abs(column - table[i]))
			return false;
	return true;
}

void bktr (vector<int> table, int row, int* solutions, vector<int>& sol) {
	for (int j = 0; j < N; j++) { 
		vector <int> clone(table);
		//cout << "parcurs " << row << " " << j << "\n";
		if (isValid(clone, row ,j )) {
			//cout << "valid " << row << " " << j << "\n";
			clone[row] = j;
			if (row == N - 1 ) {
				if(sol[0] == -2*N)
					for (int k = 0 ; k < N; k++)
							sol[k] = clone[k];
				(*solutions)++;
				return;
			}
			bktr(clone,row + 1, solutions, sol);
		}
	}
}

int main() {
	ifstream in("damesah.in");
	ofstream out("damesah.out");

	in >> N;
	vector <int> table(N,-2*N);
	vector <int> sol(N,-2*N);
	int solutions = 0;
	bktr(table, 0, &solutions, sol);
	for (int i = 0; i < N; i++)
		out << sol[i]+1 << " ";
	out << "\n" << solutions;

	in.close();
	out.close();
	//system("pause");
	return 0;
}