#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <vector>

#define UNASSIGNED 0
#define ASSIGNED 1

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int N, nr = 0;

bool Verifica(int **table, int row, int col){
	
	for(int i = 0; i < row; i++)
		if(table[i][col] == ASSIGNED)
			return false;

	for(int i = row, j = col; i >= 0 && j >= 0; i--, j--)
		if(table[i][j] == ASSIGNED)
			return false;

	for(int i = row, j = col; i >= 0 && j < N; i--, j++)
		if(table[i][j] == ASSIGNED)
			return false;

	return true;
}


bool Dame(int **table, int row){

	
	if(row >= N){
		nr++;
		
		if(nr == 1){
			for(int i = 0; i < N; ++i){
				for(int j = 0; j < N; ++j){
					if(table[i][j] == ASSIGNED)
						out << j+1 << ' ';
				}
			}
		}
		
	}

	for(int i = 0; i < N; ++i){

		if(Verifica(table, row, i) == true){

			table[row][i] = ASSIGNED;

			if(Dame(table, row+1) == true)
				return true;

			table[row][i] = UNASSIGNED;
		}
	}
	return false;
}

int main(){

	in >> N;
	int **table = new int*[N];

	for(int i = 0; i < N; ++i)
		table[i] = new int[N];

	for(int i = 0; i < N; ++i)
		for(int j = 0; j < N; ++j)
			table[i][j] = UNASSIGNED;
	
	Dame(table, 0);

	out << "\n" << nr;

	for(int i = 0; i < N; ++i)
		delete[] table[i];
	delete[] table;

	return 0;
}