#include <fstream>
#define DEF 15

using namespace std;

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

int N[DEF][DEF], n, nr, v[DEF],
di[] = {1, -1, 0, 0, 1, -1, -1, 1},
dj[] = {1, -1, 1, -1, 0, 0, 1, -1};

void mark (int x, int y) {
    for (int d =0 ; d <= 7; d++)
        for (int i = x, j = y; j <= n && i <= n && j >= 1 && i >= 1; j += dj[d], i += di[d])
            N[i][j]++;
}

void demark (int x, int y) {
    for (int d =0 ; d <= 7; d++)
        for (int i = x, j = y; j <= n && i <= n && j >= 1 && i >= 1; j += dj[d], i += di[d])
            N[i][j]--;
}


void _back (int x, int y, int t) {
    if (t == 0) {
        nr++;
        if (nr == 1) {
            for (int i = 1; i <= n; i++)
                fout << v[i] << " ";
            fout << "\n";
        }
        return;
    }
    if (y > n) {
        _back (x + 1, 1, t);
        return;
    }
    if (x > n)
        return;
    if (N[x][y] != 0) {
        _back (x, y + 1, t);
        return;
    }
    mark (x, y);
    v[x] = y;
    _back (x + 1, 1, t - 1);
    demark (x, y);
    v[x] = 0;
    _back (x, y + 1, t);
}

int main () {
    fin >> n;
    _back (1, 1, n);
    fout << nr;
    return 0;
}