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

vector<int> a, v;
int m = 0;

bool valid(int n, int v) {
    for (int i = 0; i < n; i++) {
        if ( n-i == abs(a[i] - v) ) {
            return false;
        }
    }
    return true;
}

void solve(int k) {
    if (k == a.size()) {
        m++;
        if(v.size() == 0) {
            v = a;
        }
        return;
    }
    for (int i = k; i < a.size(); i++) {
        if (valid(k, a[i])) {
            swap(a[i], a[k]);
            solve(k+1);
            swap(a[i], a[k]);
        }
    }
}

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);
    }
    solve(0);
    for (int i = 0; i < v.size(); i++) {
        cout<<v[i]<<" ";
    }
    cout<<"\n";
    cout<<m;
}