#include<iostream>
#include<fstream>
#include<math.h>
#define max 14
using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int valid(int k, int*v){
	for(int i=0;i<k;i++)
		if((abs(v[k]-v[i])==(k-i)) || (v[i]==v[k]))
			return 0;
	return 1;
}

void afisare(int n, int *v, int &counter){
	if(counter == 1)
	{
		for(int i=0;i<n;i++){
			g<<v[i]+1<<" ";
		}
	}
}

void bkt(int k, int n, int *v, int &counter){
	for(int i=0;i<n;i++){
		v[k]=i;
		if(valid(k,v)){
			if(k==n-1){
				counter++;
				afisare(n,v,counter);
			} else {
			bkt(k+1,n,v,counter);
			}
		}
	}
}

int main(){

	int n, v[max], counter = 0;
	f>>n;
	bkt(0,n,v,counter);
	g<<endl<<counter;
	f.close();
	g.close();
	return 0;
}