#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, i, contor=0;
vector <int> v;	
bool as = false, as2= false;

bool checksol(){
	int j, k, line, col;
	int a[15][15] = {{0}};

	for(i=0; i<n; i++)
		a[i+1][v[i]] = 1;

	for(i=0; i<n; i++){
		line = i+1;
		col = v[i];
		for(j=1; j<n;j++){
			if((col +j <= n) && (line + j <=n)){
				if(a[line+j][col+j] == 1)
					return false;
			}
			if((col-j >=1) && (line-j >=1)){
				if(a[line-j][col-j] == 1)
					return false;
			}
			if((col +j <= n) && (line - j >=1)){
				if(a[line-j][col+j] == 1)
					return false;
			}
			if((col -j >= 1) && (line + j <=n)){
				if(a[line+j][col-j] == 1)
					return false;
			}
		}
	}	
		
	return true;
}

int main(){
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
	
	scanf("%d" , &n);

	for(i=1; i<=n; i++)
		v.push_back(i);

	do{
		as = checksol();
		if(as == true){
			if(as2 == false){
				as2 = true;	
				for(i=0; i<n; i++)
					printf("%d ", v[i]);	
			}
		contor ++;
		}		
	}while(next_permutation(v.begin(), v.end()));

	printf("\n%d", contor);

	return 0;
}