///Nrx imi va datora un suc
#include <bits/stdc++.h>
using namespace std;

int n, sol;
int  ans[15], stk[15];
bool col[15], dia[60], dib[60];


inline bool check(int x, int y) {
    if(col[y])     return false;
    if(dia[x+y])   return false;
    if(dib[x-y+n]) return false;
    return true;

}
inline void place(int x, int y) {
    col[y]     = true;
    dia[x+y]   = true;
    dib[x-y+n] = true;
}
inline void displace(int x, int y) {
    col[y]     = false;
    dia[x+y]   = false;
    dib[x-y+n] = false;
}

void bkt(int k) {
    if(k > n) {
        if(!sol)
            for(int i=1; i<=n; ++i)
                ans[i] = stk[i];
        ++sol;
    }
    else {
        for(int i=1; i<=n; ++i) {
            if(check (k, i)) {
                stk[k] = i;
                place(k, i);
                bkt  (k+1);
                displace(k, i);
            }
        }
    }
}

int main(void) {
    FILE *fi = fopen("damesah.in", "r");
    FILE *fo = fopen("damesah.out", "w");

    fscanf(fi,"%d",&n);

    bkt(1);

    for(int i=1; i<=n; ++i)
        fprintf(fo,"%d ",ans[i]);
    fprintf(fo,"\n%d\n",sol);

    fclose(fi);
    fclose(fo);
    return 0;
}