#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
vector<int> x;
vector<int> solutie;
vector<vector<int>> all;
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){
	x.resize(13);
	for(int i = 1; i <= n; i++){
		x[k] = i;
		if(Valid(k) == true){
           if(k==n){
           	//print();
           	all.push_back(x);
            nr++;
           }else{
           	back(k+1);
           }
		}
	
	}
}

int main(){
	
	fin >> n;
	back(1);
	all[0].resize(n+1);
	for(int i = 1; i < all[0].size(); i++){
		fout << all[0][i]<<" ";
	}
	fout <<'\n';
	fout << nr;
	return 0;
}