#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
//#define f cin
#define NMAX 100001
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, n_digit;
int c_min;
int v[100];
int c[100];
int cnt;
int v1[100];
int v2[100];
int vis[100];

void afisare() {
    if (cnt == 0) {
        for (int i = 1; i <= n; ++i) {
            g << v[i] << " ";
        }
    }
}

bool valid(int k) {
    if (vis[v[k]]) return false;
    if (v1[v[k] - k + n]) return false;
    if (v2[v[k] + k]) return false;
    return true;
}

void bk(int k) {
    for (int i = 1; i <= n; ++i) {
        v[k] = i;
        if (valid(k)) {
            vis[v[k]] = 1;
            v1[v[k] - k + n] = 1;
            v2[v[k] + k] = 1;
            if (k == n) {
                afisare();
                cnt ++;
            } else bk(k + 1);
            vis[v[k]] = 0;
            v1[v[k] - k + n] = 0;
            v2[v[k] + k] = 0;
        }
    }
}


int main() {

    f >> n;
    bk(1);
    if (cnt != 0) {
        g << "\n" << cnt;
    }

    return 0;
}