// https://www.infoarena.ro/problema/damesah

#include <bits/stdc++.h>

using namespace std;

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

bool este_valid(int col, vector<int> &curent)
{
    int line = curent.size();
    for(int lineOld = 0; lineOld < curent.size(); lineOld++)
    {
        int colOld = curent[lineOld];
        if(colOld == col) return false;
        if(abs(lineOld - line) == abs(colOld - col)) return false;
    }
    return true;
}

void backtrack(vector<vector<int>> &rasp, vector<int> &curent, int n)
{
    if(curent.size() == n)
    {
        rasp.push_back(curent);
        return;
    }

    for(int col = 0; col < n; col++)
    {
        if(este_valid(col, curent))
        {
            curent.push_back(col);
            backtrack(rasp, curent, n);
            curent.pop_back();
        }
    }
}

int main()
{
    int n;
    in >> n;
    vector<vector<int>> rasp;
    vector<int> curent;
    backtrack(rasp, curent, n);
    for(int v : rasp[0])
    {
        out << v + 1 << " ";
    }
    out << "\n";
    out << rasp.size() << "\n";
    return 0;
}