#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

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

#define NMax 15
#define NrDMax NMax * 2

int n;
int col[NMax];
int c[NMax];
int ds[NrDMax], dd[NrDMax];
int nrsol;

void plaseaza(int);
void afisare();

int main(){
	fin >> n;
	plaseaza(1);
	fout << '\n' << nrsol;
}

void plaseaza(int k){
	int i, j, ok;
	if(k == n + 1){
		nrsol++;
		if(nrsol == 1) afisare();
	}
	else
		for(i = 1; i <= n; i++){
			if(c[i]) continue;
			if(ds[k - i + n] || dd[k + i - 1]) continue;
			c[i] = k;
			ds[k - i + n] = 1;
			dd[k + i - 1] = 1;
			col[k] = i;
			plaseaza(k + 1);
			c[i] = 0;
			ds[k - i + n] = 0;
			dd[k + i - 1] = 0;
		}
}

void afisare(){
	int i;
	for(i = 1; i <= n; i++)
		fout << col[i] << ' ';
}