#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int x[13];
int solutie[13];
int nr = 0;
int n;

void print() {
	for (int i = 1; i <= n; i++) {

		solutie[i] = x[i];
	
	}
	
}
	
bool Valid(int k){
	
	for (int i = 1; i < k; i++)
		if ((x[k] == x[i]) || (k - i == abs(x[k] - x[i]))){
			return false;
	}

	return true;
	
}
void back(int k){
	for(int i = 1; i <= n; i++){
		x[k] = i;
		if(Valid(k) == true){
           if(k==n){
           	print();
            nr++;
           }else{
           	back(k+1);
           }
		}
	}
	if(nr == 1 && k == n){
		for(int i = 1; i <= n; i++){
		    fout << solutie[i]<<" ";
	}
	}
}

int main(){
	
	fin >> n;
	back(1);
	
	fout <<'\n';
	fout << nr;
	return 0;
}