# include <bits/stdc++.h>
using namespace std;

int poz[15], g[123];
bool c[50], dl[50], dr[50];

int n;
int ans = 0;

void dv(int l) {
    if (l == n + 1) {
        if (ans == 0)
            for (int i = 1; i <= n; ++i)
                g [i] = poz[i];
        ans++;
        return; }
    for (int j = 1; j <= n; ++j) {
        if(!c[j] && !dl[l + j] && !dr[l - j + n]) {
            c[j] = dl[l + j] = dr[l - j + n] = 1;
            poz[l] = j;
            dv(l + 1);
            c[j] = dl[l + j] = dr[l - j + n] = 0; } } }

int main() {
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    scanf("%d", &n);

    dv(1);

    for(int i = 1; i <= n; ++i)
        printf("%d ", g[i]);
    printf("\n%d\n", ans);
    return 0; }