#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<iostream>
#include<vector>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define MOD 1000000007
using namespace std;
int N,a[20],v1[20],v2[40],v3[40];
int ok,cnt;

void backy(int k) {
    if(k == N+1) {
        if(!ok) {
            ok = 1;
            for(int i=1;i<=N;++i) {
                printf("%d ",a[i]);
            }
        }
        ++cnt;
        return;
    }
    for(int i=1;i<=N;++i) {
        if(!v1[i] && !v2[i+k] && !v3[i+N-k]) {
            a[k] = i;
            v1[i] = 1;
            v2[i+k] = 1;
            v3[i+N-k] = 1;
            backy(k+1);
            v1[i] = 0;
            v2[i+k] = 0;
            v3[i+N-k] = 0;
        }
    }
}

int main() {
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
	scanf("%d",&N);
    backy(1);
    printf("\n%d\n",cnt);
    return 0;
}