#include <bits/stdc++.h>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, r;
int p[27], d1[27];
int c[27], d2[27];

static inline void afis() {
    r++;
    if(r == 1) {
        for(int i = 1; i <= n; i++) fout << p[i] << " ";
        fout << "\n";
    }
}

static inline void Back(int k) {
    for(int i = 1; i <= n; i++) {
        if(c[i] + d1[n + k - i] + d2[k + i] == 0) {
            p[k] = i;
            c[i] = d1[n + k - i] = d2[k + i] = 1;
            if(k < n) Back(k + 1);
            else afis();
            c[i] = d1[n + k - i] = d2[k + i] = 0;
        }
    }
}

int main() {
    fin >> n;
    Back(1);
    fout << r;

    return 0;
}