#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N;

bool isValid(vector< vector<int> > matrix, int row, int column) {
	for (int i = 0; i < N; i++)
		if (i != row && matrix[i][column] == 1)
			return false;

	for (int i = 0; i < N; i++)
		if (i != column && matrix[row][i] == 1)
			return false;

	if (row > column) {
		// diagonala principala +/-1 pe linii +/-1 pe coloane
		for (int i = column - 1; i >= 0 ; i--)
			if (matrix[i + row - column][i] == 1)
				return false;
		for (int i = row + 1; i < N ; i++)
			if (matrix[i][i + column - row] == 1)
				return false;
	}
	else {
		// diagonala principala +/-1 pe linii +/-1 pe coloane
		for (int i = row - 1; i >= 0 ; i--)
			if (matrix[i][i + column - row] == 1)
				return false;
		for (int i = column + 1; i < N ; i++)
			if (matrix[i + row - column][i] == 1)
				return false;
	}

	if (row + column >= N) {
		for (int i = row + 1; i < N; i++)
			if (matrix[i][column - i + row] == 1)
				return false;

		for (int i = column + 1 ; i < N; i++)
			if (matrix[row - i + column][i] == 1)
				return false;
	}
	else {
		for (int i = row - 1; i >= 0; i--)
			if (matrix[i][column - i + row] == 1)
				return false;

		for (int i = column - 1 ; i >= 0; i--)
			if (matrix[row - i + column][i] == 1)
				return false;
	}
	return true;
}

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

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

	in >> N;
	vector < vector<int> > matrix (N, vector<int> (N, 0));
	vector <int> sol(N,0);
	int solutions = 0;
	bktr(matrix,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;
}