#include<fstream>
#include<string.h>

using namespace std;

#define max_n 15

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

int sol , n;
bool found_sol;
int V[max_n] , Sol[max_n];
int Col[max_n] , Diagonala1[2*max_n] , *D1 , D2[2*max_n];

void back( int line ){
	
	if( line > n ){
		
		sol++;
		
		if( !found_sol ){
			found_sol = true;
			memcpy(Sol , V , sizeof(Sol));
		}
		
		return;
	}
	
	int x;
	
	for( int i = 1 ; i <= n ; i++ ){
		
		if( Col[i] == 0 && D1[line - i] == 0 && D2[line + i] == 0 ){
			Col[i] = 1; D1[line - i] = 1; D2[line + i] = 1;
			V[line] = i; 
			back(line + 1);
			V[line] = 0;
			Col[i] = 0; D1[line - i] = 0; D2[line + i] = 0;
		}
		
	}
	
}


int main(){
	
	f>>n;
	
	D1 = Diagonala1 + max_n;
	
	back(1);
	
	for( int i = 1 ; i <= n ; i++ )
		g<<Sol[i]<<" ";
	g<<"\n";
	
	g<<sol<<"\n";
	
	return 0;
}