#include <stdio.h>
#define MAX 15

int n, a[MAX], nr;

void bk(int k, int v);

int main(){
	scanf("%d", &n);
	bk(1, 1);
	printf("\n%d\n", nr);
	return 0;
}

void bk(int k, int v){
	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);
	int i, ind = 0;
	if(v > n)
		return;
	for(i = 1; i < k; i++)
		if(a[i] == v || a[i] == v - (k - i) || a[i] == v + (k - i)){
			ind = 1;
			break;
		}

	if(ind == 1)
		bk(k, v + 1);
	else{
		a[k] = v;
		if(k == n){
			nr++;
			if(nr == 1)
				for(i = 1; i <= n; i++)
					printf("%d ", a[i]);
			bk(k, v + 1);
		}
		else{
			bk(k + 1, 1);
			bk(k, v + 1);
		}
	}
}