#include <fstream>

using namespace std;

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

int n, x[20], v[20][20], nr;

void afisare(){
    for (int i = 1; i <= n; ++i) {
        fout << x[i] << ' ';
    }
    fout << "\n";
}

void back(int k){
    if (k == n + 1) {
        if(nr == 0) {
            afisare();
        }
        nr++;
    } else {
        for (int i = 1; i <= n; ++i) {
            if (v[k][i] == 0) {
                x[k] = i;
                for (int j = k + 1, p = 1; j <= n; ++j, ++p) {
                    v[j][i]++;
                    if (i + p <= n) {
                        v[j][i + p]++;
                    }
                    if (i - p > 0) {
                        v[j][i - p]++;
                    }
                }
                back(k+1);
                for (int j = k + 1, p = 1; j <= n; ++j, ++p) {
                    v[j][i]--;
                    if (i + p <= n) {
                        v[j][i + p]--;
                    }
                    if (i - p > 0) {
                        v[j][i - p]--;
                    }
                }
            }
        }
    }
}

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