#include <stdio.h>
#define NMAX 15

using namespace std;

int n, queenCol[NMAX], countConfig;
bool col[NMAX], mainDiag[2*NMAX], secDiag[2*NMAX];

void placeQueen(int k) {
    if (k > n) {
        ++countConfig;
        if (countConfig == 1) {
            for (int i = 1; i <= n; ++i) printf("%d ", queenCol[i]);
            printf("\n");
        }

        return;
    }

    for (int c = 1; c <= n; ++c) {
        if (!col[c] && !mainDiag[c - k + n] && !secDiag[k + c]) {
            queenCol[k] = c;

            col[c] = mainDiag[c - k + n] = secDiag[k + c] = true;
            placeQueen(k+1);
            col[c] = mainDiag[c - k + n] = secDiag[k + c] = false;
        }
    }
}

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

    scanf("%d", &n);
    fclose(stdin);

    placeQueen(1);

    printf("%d\n", countConfig);
    fclose(stdout);
    return 0;
}