#include <iostream>
#include <fstream>
#define NMAX 13

using namespace std;

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

int n, nrSol;
int dama[NMAX], col[NMAX], mainDiag[2 * NMAX], secDiag[2 * NMAX];

void bck(int i)
{
    if (i == n) {
        if (nrSol == 0) for (int i = 0; i < n; ++i) fout << dama[i] + 1 << " ";
        ++nrSol;
    }
    else {
        for (int j = 0; j < n; ++j)
        if (!col[j] && !mainDiag[j - i + n - 1] && !secDiag[i + j]) {
                dama[i] = j;
                col[j] = mainDiag[j - i + n - 1] = secDiag[i + j] = true;
                bck(i + 1);
                col[j] = mainDiag[j - i + n - 1] = secDiag[i + j] = false;
        }
    }
}
int main()
{
    fin >> n;
    bck(0);
    fout << '\n' << nrSol;
}