#include <bits/stdc++.h>

#include <random>

using namespace std;

int solutie[15];
int visitedColumns[15];
int visitedDiagP[30];
int visitedDiagS[30];

int fromCellToDiagP(int x, int y, int n) {
    return x - y + n;
}

int fromCellToDiagS(int x, int y, int n) {
    return x + y - 1;
}

void backtracking(int current, int n, int &numberOfSolutions) {
    if (current == n + 1) {
        numberOfSolutions++;
        if (numberOfSolutions == 1) {
            for (int i = 1; i <= n; ++i) {
                cout << solutie[i] << " ";
            }
            cout << '\n';
        }
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (visitedColumns[i]) continue;
        if (visitedDiagP[fromCellToDiagP(current, i, n)]) continue;
        if (visitedDiagS[fromCellToDiagS(current, i, n)]) continue;

        solutie[current] = i;
        visitedColumns[i] = 1;
        visitedDiagP[fromCellToDiagP(current, i, n)] = 1;
        visitedDiagS[fromCellToDiagS(current, i, n)] = 1;

        backtracking(current + 1, n, numberOfSolutions);

        visitedColumns[i] = 0;
        visitedDiagP[fromCellToDiagP(current, i, n)] = 0;
        visitedDiagS[fromCellToDiagS(current, i, n)] = 0;
    }
}

signed main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    int n, answer = 0;
    cin >> n;
    backtracking(1, n, answer);
    cout << answer << '\n';
    return 0;
}