#include <stdio.h>
#include <stdlib.h>
#define MAXN 14

#define IN "damesah.in"
#define OUT "damesah.out"

int diag1 [MAXN], diag2 [MAXN], col [MAXN], n, sol = 0, solCount = 0;

inline int good (int lev){
    int i;
    for (i = 1; i < lev; ++ i)
        if (diag1[i] == diag1[lev] || col[i] == col[lev] ||diag2[i] == diag2[lev])
            return 0;
    return 1;
}

void printSolution (void){
    int i;
    for (i = 1; i <= n; ++ i)
        printf ("%d ", col[i]);
}

void BT (int lev){
    if (lev - 1 == n){
        ++ solCount;
        if (!sol){
            sol = 1;
            printSolution();
        }
    }
    else{
        int i;
        for (i = 1; i <= n; ++i){
            diag1 [lev] = lev - i;
            diag2 [lev] = lev + i;
            col [lev] = i;
            if (good (lev))
                BT (lev + 1);
        }
    }
}

int main(void){
    freopen (IN, "r", stdin);
    freopen (OUT, "w", stdout);

    scanf ("%d", &n);
    BT(1);
    printf ("\n%d", solCount);
    fclose (stdin);
    fclose (stdout);
    return 0;
}