#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, seen [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 (! seen[i]){
                //diag1 [lev] = lev - i;
                //diag2 [lev] = lev + i;
                col [lev] = i;
                seen [i] = 1;
                if (good (lev))
                    BT (lev + 1);
                seen [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;
}