#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

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

int n, sol[20], nr, mat[20][20];
bool lin[15], diag1[30], diag2[30];

bool okok (int l, int c) {
    if (lin[l])
    return false;

    if (diag1[l+c-1])
        return false;

    if (diag2[n-c+l])
        return false;

    return true;
}
void solve (int poz) {
    if (poz > n) {
        if (nr == 0)
            for (int i = 1; i <= n; i++)
            fout << sol[i] << " ";
        nr++;
    }

    for (int i = 1; i <= n; i++) {
        if (okok(i, poz)) {
            lin[i] = 1;
            mat[i][poz] = 1;
            sol[poz] = i;
            diag1[i+poz-1] = 1;
            diag2[n-poz+i] = 1;
            solve(poz+1);
            mat[i][poz] = 0;
            lin[i] = 0;
            diag1[i+poz-1] = 0;
            diag2[n-poz+i] = 0;
        }
    }

}


int main()
{
    fin >> n;
    solve(1);
    fout << "\n" << nr;
    return 0;
}