#include <algorithm>
#include <cstdio>

#define MaxN 15

using namespace std;

int n, poz[MaxN], cnt;
bool is_first = true, seen_lin[MaxN], seen_dig1[2 * MaxN], seen_dig2[2 * MaxN];

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++) {
            if (seen_lin[i] == false && seen_dig1[lvl + i] == false &&
                seen_dig2[MaxN + lvl - i] == false) {
                seen_lin[i] = true;
                seen_dig1[lvl + i] = true;
                seen_dig2[MaxN + lvl - i] = true;
                poz[lvl] = i;
                bkt(lvl + 1);
                poz[lvl] = 0;
                seen_lin[i] = false;
                seen_dig1[lvl + i] = false;
                seen_dig2[MaxN + lvl - i] = false;
            }
        }
    }
}

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

    scanf("%d", &n);

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

    return 0;
}