#include <bits/stdc++.h>

using namespace std;

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

int N, cnt;
vector<int>sol;
vector<bool> vizCol, vizDiagP, vizDiagS;

void Back(int k)
{
    if (k == N + 1)
    {
        if (cnt < 1)
            for (int i = 1; i < sol.size(); ++i)
                fout << sol[i] << " ";
        cnt++;
    }
    else
    {
        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);
    vizCol.resize(N << 1, false);
    vizDiagP.resize(N << 1, false);
    vizDiagS.resize(N << 1, false);

    Back(1);

    fout << "\n" << cnt;

    return 0;
}