#include<bits/stdc++.h>

using namespace std;

int n,k2;
int a[30][30];
bool v;
queue <int> Q;
bool OK(int i, int j) {
	bool u=0;
	int i2=i, j2=j;
	while (i>=1 && j>=1 && j<=n && i<=n) {
		if (a[i][j]==1) {
			u=1; break;
		}
		i--;
		j--;
		
	}
	i=i2,j=j2;
	while (i>=1 && j>=1 && j<=n && i<=n) {
		if (a[i][j]==1) {
			u=1; break;
		}
		i--;
		j++;
	}
	i=i2,j=j2;
	while (i>=1 && j>=1 && j<=n && i<=n) {
		if (a[i][j]==1) {
			u=1; break;
		}
		i--;
	}
	
	if (u) return 0;
	return 1;
}

void BT(int k) {
	if (k==n+1) {
		k2++; v=1; return;
	}
	for (int j=1; j<=n; j++) {
		if (OK(k,j)) {
			a[k][j]=1;
			if (!v) Q.push(j);
			BT(k+1);
			if (!v) Q.pop();
			a[k][j]=0;
		}
		
	}
	
	
}


int main() {
	ifstream cin("damesah.in");
		ofstream cout("damesah.out");
	cin>>n;
	
	BT(1);
	while (!Q.empty()) {
		cout<<Q.front()<<" ";
		Q.pop();
	}
	cout<<'\n'<<k2;
	
}