#include <fstream>

using namespace std;

bool A[30],B[30],C[30],D[30];
int X[15],N,rs = 0;
void back(int k){
	if(k <= N){
		for(int i=1;i<=N;i++){
			if(!A[k] && !B[i] && !C[k+i] && !D[k-i+15]){
				A[k] = B[i] = C[k+i] = D[k-i+15] = true;
				if(X[N] == 0) X[k] = i;
				back(k+1);
				A[k] = B[i] = C[k+i] = D[k-i+15] = false;
			}
		}
	} else rs++;
}

int main(){
	ifstream fin("damesah.in");
	ofstream fout("damesah.out");
	fin >> N;
	back(1);
	for(int i = 1;i<=N;i++){
		fout << X[i] << ' ';
	}
	fout << '\n' << rs;
	return 0;
}