#include <fstream>
#define nmax 15
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

bool col[nmax], diag1[2 * nmax], diag2[2 * nmax];
int n, numbering, total = 0, h[nmax];

bool isOk(int i, int d1, int d2) {
    if (col[i] == true or diag1[d1] == true or diag2[d2] == true)
        return false;
    return true;
}

void write_first() {
    for (int i = 1; i <= n; ++i)
        fout << h[i] << " ";
    fout << "\n";
}

void backTrack(int row) {
    for (int i = 1; i <= n; ++i) {
        bool doesEnter = false;
        if (isOk(i, n - row + i, 2 * n - row - i + 1)) {
            doesEnter = true;
            h[row] = i;
            col[i] = diag1[n - row + i] = diag2[2 * n - row - i + 1] = true;
            ++numbering;
            if (numbering == n) {
                ++total;
                if (total == 1)
                    write_first();
            }
            else
                backTrack(row + 1);
        }
        if (doesEnter == true) {
            col[i] = diag1[n - row + i] = diag2[2 * n - row - i + 1] = false;
            --numbering;
        }
    }
}

int main()
{
    fin >> n;
    backTrack(1);
    fout << total;
    return 0;
}