#include <fstream>
#include <iostream>
using namespace std;

int n, ns, fs[13];
bool col[13], diagp[25], diags[25], genned;

void generareRegine(int lin){
	if (lin==n){
		genned=true;
		ns++;
		return;
	}

	int i;
	for (i=0; i<n; i++)
		if (col[i]==false && diagp[(i-lin)+n-1]==false && diags[i+lin]==false){
			col[i]=true; diagp[(i-lin)+n-1]=true; diags[i+lin]=true;
			if (genned==false)
				fs[lin]=i+1;
			generareRegine(lin+1);
			col[i]=false; diagp[(i-lin)+n-1]=false; diags[i+lin]=false;
		}
}

int main(){
	int i;

	ifstream fin ("damesah.in");
	fin >> n;
	fin.close();

	generareRegine(0);

	ofstream fout ("damesah.out");
	for (i=0; i<n; i++)
		fout << fs[i] << ' ';
	fout << '\n' << ns;
	fout.close();

	return 0;
}