#include    <fstream>

using namespace std;

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

#define ARRAY_MAX 100005

int N, solution;
int arr[ARRAY_MAX];
bool column[ARRAY_MAX], mainDiag[ARRAY_MAX], secDiag[ARRAY_MAX];

void backTrack(int start, int N) {
    if (start - 1 == N) {
        if (!solution) {
            for (int i = 1; i <= N; i++)
                fout << arr[i] << " ";

            fout << "\n";
        }

        solution++;
    }

    else
        for (int i = 1; i <= N; i++)
            if (!(column[i] || mainDiag[i - start + N] || secDiag[start + i])) {
                arr[start] = i;

                column[i] = true;
                mainDiag[i - start + N] = true;
                secDiag[start + i] = true;

                backTrack(start + 1, N);

                column[i] = false;
                mainDiag[i - start + N] = false;
                secDiag[start + i] = false;
            }
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> N;

    backTrack(1, N);

    fout << solution;
}