#include <bits/stdc++.h>

using namespace std;

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

int n, a, b, solCnt;
int sol[15];
bool mainDiag[30], secDiag[30], col[30];

void print()
{
    for (int i = 0; i < n; ++i)
        g << sol[i] + 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;

    bk(0);

    g << '\n' << solCnt;

    return 0;
}