#include <stdio.h>
#define MAX 15
 
int n, a[MAX], nr, col[MAX], diagp[2 * MAX], diags[2 * MAX];
 
void bk(int k);

int main(){
	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);
	scanf("%d", &n);
	bk(1);
	printf("\n%d\n", nr);
	return 0;
}
 
void bk(int k){
	int i, j;
	for(i = 1; i <= n; i++)
		if(!col[i] && !diagp[n - i + k] && !diags[i + k - 1]){
			a[k] = i;
			if(k == n){
				nr++;
				if(nr == 1)
					for(j = 1; j <= n; j++)
						printf("%d ", a[j]);
			}
			col[i] = diagp[n - i + k] = diags[i + k - 1] = 1;
			bk(k + 1);
			col[i] = diagp[n - i + k] = diags[i + k - 1] = 0;
		}
}