#include <fstream>
using namespace std;

const int MAXN = 15;

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

int col[MAXN];
bool lin[MAXN], diag1[2 * MAXN], diag2[2 * MAXN];

int n;

int rasp;

void afisare()
{
    ++rasp;
    if (rasp == 1)
        for (int i = 1;i <= n;++i)
            out << col[i] << ' ';
}

void bkt (int l)
{
    if (l > n)
        afisare();
    for (int c = 1;c <= n;++c)
    {
        if (lin[c])
            continue;

        if (diag1[l - c + n])
            continue;

        if (diag2[l + c])
            continue;

        col[l] = c;
        lin[c] = true;
        diag1[l - c + n] = true;
        diag2[l + c] = true;

        bkt(l + 1);

        lin[c] = false;
        diag1[l - c + n] = false;
        diag2[l + c] = false;
    }
}

int main()
{
    in >> n;
    bkt(1);
    out << '\n' << rasp << '\n';
    return 0;
}