#include <fstream>

using namespace std;

ifstream f("damesah.in");
ofstream o("damesah.out");

int n,sol[15],viz_col[15],viz_ds[40], viz_dd[40],c[15];

void Back(int pos) {
    if(pos == n + 1) {
        if(not sol[0])
            for(int i = 1; i <= n; ++i)
                sol[i] = c[i];
        ++ sol[0];
        return;
    }
    for(int i = 1; i <= n; ++i)
        if(not viz_col[i] && not viz_ds[i-pos+1+14] && not viz_dd[i+pos-1+14]) {
            viz_col[i] = 1;
            viz_ds[i-pos+1+14] = 1;
            viz_dd[i+pos-1+14] = 1;
            c[pos] = i;
            Back(pos+1);
            viz_col[i] = 0;
            viz_ds[i-pos+1+14] = 0;
            viz_dd[i+pos-1+14] = 0;
        }
}

int main() {
    f >> n;
    Back(1);
    for(int i = 1; i <= n; ++i)
        o << sol[i] << " ";
    o << "\n" << sol[0] << "\n";
    return 0;
}