#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

void back(vector<vector<int>>& solutii, vector<int> &solutie, vector<int> &space) {
    if (space.empty()) {
        solutii.push_back(solutie);
        return;
    }
    for (int i = 0; i < space.size(); i++) {
        int val = space[i];
        // check diagonals
        int j = 1;
        bool sat = true;
        while(solutie.size() >= j) {
            if ((solutie[solutie.size() - j] == val - j) || (solutie[solutie.size() - j] == val + j)) {
                sat = false;
                break;
            }
            j++;
        }
        if (sat == false) {
            continue;
        }
        solutie.push_back(val);
        space.erase(space.begin() + i);
        back(solutii, solutie, space);
        space.insert(space.begin() + i, val);
        solutie.pop_back();
    }
}

int main() {
    int n;
    fin >> n;
    vector<vector<int>> solutii;
    vector<int> solutie;
    vector<int> space;
    for (int i = 0; i < n; i++) {
        space.push_back(i + 1);
    }
    back(solutii, solutie, space);
    for (int j = 0; j < n; j++) {
        fout << solutii[0][j] << " ";
    }
    fout << endl;
    fout << solutii.size();
    fout << endl;
    return 0;
}