#include <stdio.h>
#include <stdlib.h>

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

int col [MAXN], n, sol = 0, solCount = 0, seenCol [MAXN] = {0}, seenDiag1 [2 * MAXN] = {0}, seenDiag2 [2 * MAXN] = {0};

inline int good (int lev){
    int i;
    for (i = 1; i < lev; ++ i)
        if (col[i] == col[lev] || col[i] + i == col[lev] + lev || col[i] - i == col[lev] - 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){
            if (!seenCol[i] && !seenDiag1[n + lev - i] && !seenDiag2[lev + i]){
                col [lev] = i;
                seenCol [i] = 1;
                seenDiag1 [n + lev - i] = 1;
                seenDiag2 [lev + i] = 1;
                BT (lev + 1);
                seenCol [i] = 0;
                seenDiag1 [n + lev - i] = 0;
                seenDiag2 [lev + i] = 0;
            }
        }
    }
}

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;
}