#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
using namespace std;

vector<int> a, v;
int m = 0;
vector<bool> b1, b2, c;

template <typename T>
void showVector(vector<T> a) {
    copy(a.begin(), a.end(), ostream_iterator<T>(cout, " "));
    cout<<"\n";
}

int diag1(int i, int j) {
    return a.size()+j-i;
}

int diag2(int i, int j) {
    return a.size()+j-(a.size()-i+1);
}

void solve(int k) {
    if (k == a.size()) {
        if (v.size() == 0) {
            v = a;
        }
        m++;
        return;
    }
    for (int i = 1; i <= a.size(); i++) {
        if (c[i]) {
            continue;
        }
        int d1 = diag1(k+1, i), d2 = diag2(k+1, i);
        if (!(b1[d1] || b2[d2])) {
            a[k]=i;
            c[i]=b1[d1]=b2[d2]=true;
            solve(k+1);
            c[i]=b1[d1]=b2[d2]=false;
        }
    }
}

int main() {
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");
    int n;
    cin>>n;
    for (int i = 0; i < n; i++) {
        a.push_back(i+1);
    }
    c.resize(n+1);
    b1.resize(2*n);
    b2.resize(2*n);
    solve(0);
    showVector(v);
    cout<<m;
}