#include <fstream>
#include <cmath>

#define MAXN 15

using namespace std;

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

short int n, x[MAXN], fr[MAXN];

inline void Read() {
    fin >> n;
}

inline short cond(int k) {
    if (fr[x[k]])
        return 0;
    for (short i = 1; i < k; i++) {
        if (abs(i - k) == abs(x[i] - x[k]))
            return 0;
    }
    return 1;
}

inline void Afisare() {
    for (short i = 1; i <= n; i++)
        fout << x[i] << " ";
}

inline void bkt() {
    int k = 1, sol = 0;

    while (k) {
        if (x[k] < n) {
            x[k]++;

            if (cond(k)) {
                if (k == n) {
                    if (!sol)
                        Afisare();
                    sol++;
                }
                else {
                    fr[x[k]] = 1;
                    k++;
                    x[k] = 0;
                }
            }
        }
        else {
            k--;
            fr[x[k]] = 0;
        }
    }

    fout << "\n" << sol;
}

int main () {
    Read();
    bkt();

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