#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ofstream os("damesah.out");

vector<int> a;
vector<bool> c, d1, d2;
int n, nr, nr2;

void write() {
    ++nr;
    if (nr == 1) {
        std::for_each(a.begin(), a.end(), [&os](const int& nr) { os << nr + 1 << " ";});
        os << "\n";
    }
}

bool ok(int i, int j) {
    return !c[j] && !d1[n - 1 + j - i] && !d2[i + j];
}

void solve(int k) {
    if (k == n) {
        write();
        return;
    }
    if (k == 0) {
        for (int i = 0; i < n / 2; ++i)
        if (ok(k, i)) {
            c[i] = true;
            d1[n - 1 + i - k] = true;
            d2[k + i] = true;
            a.push_back(i);

            solve(k + 1);

            a.pop_back();
            d1[n - 1 + i - k] = false;
            d2[k + i] = false;
            c[i] = false;
        }
        nr *= 2;
        if (!(n & 2)) {
            int i = n / 2;
            if (ok(k, i)) {
            c[i] = true;
            d1[n - 1 + i - k] = true;
            d2[k + i] = true;
            a.push_back(i);

            solve(k + 1);

            a.pop_back();
            d1[n - 1 + i - k] = false;
            d2[k + i] = false;
            c[i] = false;
            }
        }
    }
    else
        for (int i = 0; i < n; ++i)
            if (ok(k, i)) {
                c[i] = true;
                d1[n - 1 + i - k] = true;
                d2[k + i] = true;
                a.push_back(i);

                solve(k + 1);

                a.pop_back();
                d1[n - 1 + i - k] = false;
                d2[k + i] = false;
                c[i] = false;
            }
}

int main()
{
    ifstream is("damesah.in");
    is >> n;
    is.close();
    c.resize(n + 1, false);
    d1.resize(n + 1, false);
    d2.resize(n + 1, false);
    for (unsigned int i = 0; i <= n; ++i)
        c[i] = d1[i] = d2[i] = 0;
    solve(0);
    os << nr << "\n";
    os.close();
    return 0;
}