#include <cstdio>
#include <bitset>
using namespace std;

const int NMAX = 15;

bitset <NMAX> ok;
bitset <NMAX << 1> d1, d2;
int N, x[NMAX], _ans[NMAX], cnt;
bool ans = 1;

inline void make_ans () {

    for (int i = 1; i <= N; ++i)
        _ans[i] = x[i];

}

inline int pdp (const int &i, const int &j) {

    if (j > i)
        return N - j + i;
    else
        return N + i - j;

}

inline int pds (const int &i, const int &j) {

    return i + j - 1;

}

void bkt (const int &i) {

    if (i > N) {
        if (ans) {
            make_ans ();
            ans = 0;
        }
        ++cnt;
        return;
    }
    for (int k = 1; k <= N; ++k) {
        if (!ok[k] && !d1[pdp (i, k)] && !d2[pds (i, k)]) {
            x[i] = k;
            ok[k] = d1[pdp (i, k)] = d2[pds (i, k)] = 1;
            bkt (i + 1);
            ok[k] = d1[pdp (i, k)] = d2[pds (i, k)] = 0;
        }
    }

}

int main () {

    freopen ("damesah.in", "r", stdin);
    freopen ("damesah.out", "w", stdout);
    scanf ("%d", &N);
    bkt (1);
    for (int i = 1; i <= N; ++i)
        printf ("%d ", _ans[i]);
    printf ("\n%d", cnt);

}