#include <iostream>
#include <fstream>

using namespace std;
const int Nmax = 16;

int N;
//int r[Nmax];    // rows
int c[Nmax];    // cols
int d1[2*Nmax]; // [\] - diagonals
int d2[2*Nmax]; // [/] - diagonals

int lex = 0;
int cnt = 0;
int path[Nmax];
int res[Nmax];  // first result

void doit(int i) // proces row i
{
    if (i == N) {
        cnt++;
        if (!lex) {
            lex = 1;
            for(int n = 0; n < N; n++)
                res[n] = path[n] + 1;
        }
        return;
    }
    for (int j = 0; j < N; j++)
    {
        if (c[j] == 0 && d1[i-j+N-1] == 0 && d2[i+j] == 0)
        {
            path[i] = j;
            c[j] = 1; d1[i-j+N-1] = 1; d2[i+j] = 1;
            doit(i+1);
            c[j] = 0; d1[i-j+N-1] = 0; d2[i+j] = 0;
        }
    }
}

int main()
{
    ifstream f ("damesah.in");
    ofstream g ("damesah.out");
    f >> N;
    
    for (int i = 0; i < N; i++) {
        //r[i]  = 0;
        c[i]  = 0;

        d1[2*i] = 0;   d1[2*i+1] = 0;
        d2[2*i] = 0;   d2[2*i+1] = 0;
        path[i] = 0;
    }
    
    doit(0);
    for (int i = 0; i < N; i++)
        g << res[i] << (i < N-1 ? ' ':'\n');

    g << cnt << endl;
    return 0;
}