#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int nr_sol = 0;

void bkt(int k, int n, vector<int> &st, vector<int> &visited, ofstream &fout) {
    if (k == n + 1) {
        nr_sol++;
        if (nr_sol == 1) {
            for (int i = 1; i <= n; i++) {
                fout << st[i] << ' ';
            }
            fout << endl;
        }
        return;
    }

    for (int i = 1; i <= n; i++) {
        st[k] = i;

        int ok = 1;
        if (visited[i] == 1) {
            ok = 0;
        }

        if (ok) {
            for (int j = 1; j < k; j++) {
                if (abs(k - j) == abs(st[k] - st[j])) {
                    ok = 0;
                    break;
                }
            }
        }

        if (ok) {
            visited[i] = 1;
            bkt(k + 1, n, st, visited, fout);
            visited[i] = 0;
        }
    }
}

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

    int n;
    fin >> n;

    vector<int> st(n + 1, 0);
    vector<int> visited(n + 1, 0);

    bkt(1, n, st, visited, fout);

    fout << nr_sol << endl;

    fin.close();
    fout.close();
    return 0;
}