#include <iostream>
#include <fstream>

using namespace std;

int n, nrSol;
int a[30];
bool col[30], dp[200], ds[200];

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

void BackTrack(int k) {
    if (k > n) {
        nrSol++;
        if (nrSol == 1) {
            for (int i = 1; i <= n; i++) {
                fout << a[i] << ' ';
            }
            fout << '\n';
        }
    }
    for (int i = 1; i <= n; i++) {
        if (col[i] == 0 && ds[k + i] == 0 && dp[k - i + n] == 0) {
            a[k] = i;
            col[i] = ds[k + i] = dp[k - i + n] = true;
            BackTrack(k + 1);
            col[i] = ds[k + i] = dp[k - i + n] = false;
        }
    }
}

int main()
{
    fin >> n;
    BackTrack(1);
    fout << nrSol;
    return 0;
}