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

vector<int> a, firstSolution;
int countSolutions;

bool isGood(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if ( abs(i-j) == abs(a[i] - a[j]) ) {
                return false;
            }
        }
    }
    return true;
}

void generateSolutions(int k) {
    if (k >= a.size()) {
        if (isGood(a.size())) {
            countSolutions++;
            if(firstSolution.size() == 0) {
                firstSolution = a;
            }
        }
        return;
    }
    for (int i = k; i < a.size(); i++) {
        swap(a[i], a[k]);
        if (isGood(k+1)) {
            generateSolutions(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);
    }
    generateSolutions(0);
    for (int i = 0; i < firstSolution.size(); i++) {
        cout<<firstSolution[i]<<" ";
    }
    cout<<"\n";
    cout<<countSolutions;
}