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

using namespace std;

int n, i, contor=0;
int v[15];
bool as = false, as2= false;

bool checksol(){
	int j, k, line, col;

	//for(i=0; i<n; i++)
	//	for(j=i+1; j<n;j++)
	//		if(j-i == abs(v[j] - v[i]))
				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[i-1] = 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, v+n));

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

	return 0;
}