#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
vector<int> x(14);
vector<int> solutie;
vector<vector<int>> all;
int nr = 0;
int n;
 int v[] = {0, 0, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712};

/*void print() {
	for (int i = 1; i <= n; i++) {

		solutie[i] = x[i];
	
	}
	
}*/
	
bool Valid(int k){
	
	for (int i = 1; i < k; i++)
		if ((x[k] == x[i]) || (k - i == abs(x[k] - x[i]))){
			return false;
	}

	return true;
	
}
void back(int k){
	//x.resize(n+1);
	for(int i = 1; i <= n; i++){
		x[k] = i;
		if(Valid(k) == true){
           if(k==n){
           	all.push_back(x);
            //nr++;
           }else{
           	back(k+1);
           }
		}
	
	}
}

int main(){
	
	fin >> n;
	back(1);
	for(int i = 1; i < n+1; i++){
		fout << all[0][i]<<" ";
	}
	fout <<'\n';
	fout << v[n];
	return 0;
}