#include <bits/stdc++.h>

using namespace std;

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

int N, cnt;
vector<int>sol;
bool vizCol[1 << 5], vizDiagP[1 << 5], vizDiagS[1 << 5];

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 (int i = 1; i <= N; ++i)
            if (!vizCol[i] && !vizDiagP[k + i] && !vizDiagS[i - k + N])
            {
                sol[k] = i;
                vizCol[i] = true; vizDiagP[k + i] = true; vizDiagS[i - k + N] = true;
                Back(k + 1);
                vizCol[i] = false; vizDiagP[k + i] = false; vizDiagS[i - k + N] = false;
            }


}

int main()
{
    fin >> N;

    sol.resize(N + 1);


    Back(1);

    fout << "\n" << cnt;

    return 0;
}