#include <bits/stdc++.h>

using namespace std;

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

int n, a, b, solCnt;
vector<int> sol;
vector<bool> mainDiag, secDiag, col;

void print()
{
    for (auto x : sol)
        g << x + 1 << ' ';
}

bool valid(int index)
{
    return !col[sol[index]] && !mainDiag[n - 1 + sol[index] - index] && !secDiag[sol[index] + index];
}

void bk(int index)
{
    for (sol[index] = 0; sol[index] < n; ++sol[index])
        if (valid(index))
            if (index == n - 1)
            {
                ++solCnt;
                if (solCnt == 1)
                    print();
            }
            else
            {
                col[sol[index]] = mainDiag[n - 1 + sol[index] - index] = secDiag[sol[index] + index] = true;
                bk(index + 1);
                col[sol[index]] = mainDiag[n - 1 + sol[index] - index] = secDiag[sol[index] + index] = false;
            }
}

int main()
{
    f >> n;
    sol.resize(n);
    col.resize(n, 0);
    mainDiag.resize(2 * n, 0);
    secDiag.resize(2 * n), 0;

    bk(0);

    g << '\n' << solCnt;

    return 0;
}