#include <cstdio>
#include <bitset>
using namespace std;
int x[20];
bitset<40> f,p,s;
int n,sol;
void bt(int k) {
    if (k>n) {
        sol++;
        if (sol==1) {
			for (int i=1;i<=n;i++)
				printf("%d ",x[i]);
        }
        return;
    }
    for (int i=1;i<=n;i++) {
        x[k]=i;
        if (!p[n+i-k]&&!s[i+k]&&!f[i]) {
			f[i]=1, p[n+i-k]=1, s[i+k]=1;
			bt(k+1);
			f[i]=0, p[n+i-k]=0, s[i+k]=0;
        }
    }
}
int main() {
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    bt(1);
    printf("\n%d",sol);
    return 0;
}