#include <iostream>
	
#include <math.h>
	
#include<fstream>
	
using namespace std;
	
 
	
 
	
int x[13];
	
int solutie[13];
	
 
	
 
	
 
	
void tiparesteSolutie(int n) {
	
	for (int i = 1; i <= n; i++) {
	
		solutie[i] = x[i];
	
	}
	
}
	
 
	
bool eValid(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;
	
}
	
 
	
int backtrack(int n){
	
	int eSolutie, k;
	
	k = 1;
	
	x[k] = 0;
	
	int nrSolutii = 0;
	
	int prima = 1;
	
	while (k > 0) {
	
		eSolutie = 0;
	
		while ((x[k] < n) && (!eSolutie)) {
	
			x[k]++;
	
			eSolutie = eValid(k);
	
		}
	
		if (!eSolutie){
	
			k--;
	
		}
	
		else{
	
			if (k == n) {
	
				if (prima)
	
				{
	
					tiparesteSolutie(n);
	
					prima = 0;
	
				}
	
				nrSolutii++;
	
			}
	
			else {
	
				k++;
	
				x[k] = 0;
	
			}
	
		}
	
	}
	
	return nrSolutii;
	
}
	
 
	
int main() {
	
	ofstream o("damesah.out");
	
	ifstream f("damesah.in");
	
	int n, k, eSolutie;
	
	f >> n;
	
	int nrSolutii = backtrack(n);
	
	for (int i = 1; i <= n; i++){
	
		o << solutie[i] << " ";
	
	}
	
	o << '\n';
	
	o << nrSolutii;
	
	return 0;
	
}