#include <algorithm>
#include <cstdio>

#define MaxN 15

using namespace std;

int n, poz[MaxN], cnt;
bool is_first = true;

bool valid(int n) {
    for (int i = 1; i < n; i++) {
        if (poz[i] == poz[n] || poz[i] - i == poz[n] - n ||
            poz[i] + i == poz[n] + n)
            return false;
    }
    return true;
}

void bkt(int lvl) {
    if (lvl == n + 1) {
        if (is_first) {
            for (int i = 1; i <= n; i++) {
                printf("%d ", poz[i]);
            }
            printf("\n");
            is_first = false;
        }
        cnt++;
    } else {
        for (int i = 1; i <= n; i++) {
            poz[lvl] = i;
            if (valid(lvl)) {
                bkt(lvl + 1);
            }
            poz[lvl] = 0;
        }
    }
}

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

    scanf("%d", &n);

    bkt(1);
    printf("%d\n", cnt);

    return 0;
}