#include <iostream>
#include <math.h>
#include <fstream>

using namespace std;

int x[13];
int m[13];

void f1(int n) {
	for (int i=1;i<=n;i++) {
		m[i]=x[i];
	}
}

bool f2(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 f3(int n){
	int me,k;
	k=1;
	x[k]= 0;
	int db=0;
	int elso=1;
	while (k>0) {
		me=0;
		while ((x[k]<n)&&(!me)) {
			x[k]++;
			me=f2(k);
		}
		if (!me) k--;
		else{
			if(k==n) {
				if(elso)
				{
					f1(n);
					elso=0;
				}
				db++;
			}
			else {
				k++;
				x[k]=0;
			}
		}
	}
	return db;
}

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

int main() {
	int n,k,e;
	fin>>n;
	int db=f3(n);
	for (int i=1;i<=n;i++){
		fout<<m[i]<<" ";
	}
	fout<<endl;
	fout<<db;
	return 0;
}