#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

bool is_config_valid(const std::vector<int> &a, int n)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (abs(a[i] - a[j]) == j - i)
            {
                return false;
            }
        }
    }
    return true;
}

pair<vector<int>, int> n_queen_solution(int n)
{
    vector<int> a(n);
    vector<int> sol(n);
    bool found = false;
    for (int i = 0; i < n; ++i)
    {
        a[i] = i;
    }
    int cnt = 0;
    do
    {
        if (is_config_valid(a, n))
        {
            if (!found)
            {
                copy(a.begin(), a.end(), sol.begin());
                found = true;
            }
            ++cnt;
        }
    } while (next_permutation(a.begin(), a.end()));
    return {sol, cnt};
}

int main()
{
    int n;
    fin >> n;
    pair<vector<int>, int> result = n_queen_solution(n);
    for (int i = 0; i < n; ++i)
    {
        fout << result.first[i] + 1 << " ";
    }
    fout << "\n" << result.second << "\n";
    return 0;
}