#include <bits/stdc++.h>

using namespace std;

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

int N, cnt;
vector<int>sol;

bool valid(int k)
{
    if (k == 1)
        return true;

    for (int i = 1; i < k; ++i)
        if (sol[i] == sol[k] || k - i == abs(sol[k] - sol[i]))
            return false;
    return true;
}

void Back(int k)
{
    if (k == N + 1)
    {
        if (cnt < 1)
            for (int i = 1; i < sol.size(); ++i)
                fout << sol[i] << " ";
        cnt++;
        return;
    }
    for (sol[k] = 1; sol[k] <= N; ++sol[k])
        if (valid(k))
            Back(k + 1);
}

int main()
{
    fin >> N;

    sol.resize(N + 1);

    Back(1);

    fout << "\n" << cnt;

    return 0;
}