#include<iostream>
#include<fstream>

using namespace std;
const int MAX=13;
bool col[MAX+1], main_diag[MAX*2], sec_diag[MAX*2];
int ans, queens[MAX+1];

void bck(FILE *out, int l, int n){
    if(l==n+1){
    	ans++;
		if(ans==1) 
    	  for(int i=1;i<=n;i++)  fprintf(out,"%i ",queens[i]);
	} 
	else
	  for(int c=1;c<=n;c++){
	     if(!col[c] && !main_diag[c-l+n] && !sec_diag[l+c-1]){
	     	queens[l]=c; 
	     	col[c]=main_diag[c-l+n]=sec_diag[l+c-1]=true;
	     	bck(out,l+1,n);
	     	col[c]=main_diag[c-l+n]=sec_diag[l+c-1]=false;
		 }	
	  }
}

int main(){
int n;	
ifstream in("damesah.in");
in>>n;
in.close();
FILE *out=fopen("damesah.out","w");
bck(out,1,n);
fprintf(out,"\n%i",ans);
fclose(out);
return 0;	
}