#include <stdio.h>

int n, solNumber;
int sol[14];
bool col[14], diag[28], secDiag[28];
bool tabla[14][14];

void saveSol() {
    sol[0] = 1;
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k) {
            if(tabla[j][k]) {
                sol[j] = k;
                break;
            }
        }
}

bool isInDanger(int i, int j) {
    return col[j] ||
            tabla[i][j] ||
            diag[i + j -1] ||
            secDiag[n - i + j];
}

void setOccupied(int i, int j, bool occupied) {
    tabla[i][j] = occupied;
    col[j] = occupied;
    diag[i + j - 1] = occupied;
    secDiag[n - i + j] = occupied;
}

void backtrack(int i) {
    if(i == n + 1) {
        if(sol[0] == 0) 
            saveSol();

        ++solNumber;
        return;
    }

    for(int j = 1; j <= n; ++j) {
        if(!isInDanger(i, j)) {
            setOccupied(i, j, true);
            backtrack(i+1);
            setOccupied(i, j, false);
        }
    }
}

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

    scanf("%d", &n);

    backtrack(1);

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