#include <stdio.h>
#include <stdlib.h>
#define MAX 13
int v[MAX],n,cnt;
FILE *fin, *fout;
void afisare () {
    int i;
    cnt++;
    if (cnt==1) {
        for (i=1; i<=n; i++) {
            fprintf(fout, "%d ", v[i]);
        }
        fprintf(fout, "\n");
    }
}
int ok (int k) {
    int i;
    for (i=1; i<k; i++) {
        if (v[i]==v[k]) {
            return 0;
        }
        if ((k-i)==(v[k]-v[i]) || (k-i)==(v[i]-v[k])) {
            return 0;
        }
    }

    return 1;
}
void regina (int k) {
    int i;
    for (i=1; i<=n; i++) {
        v[k]=i;
        if (ok(k)==1) {
            if (k==n) {
                afisare();
            } else {
                regina(k+1);
            }
        }
    }
}
int main() {
    fin=fopen("damesah.in","r");
    fout=fopen("damesah.out","w");
    fscanf(fin, "%d", &n);
    cnt=0;
    regina(1);
    fprintf(fout, "%d\n", cnt);
    fclose(fin);
    fclose(fout);
    return 0;
}