// Sa se aranjeze n dame pe o tabla de sah n*n astfel incat sa nu se atace.

#include <fstream>
#include <cmath>

using namespace std;

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

int v[15], solutie[15];

void creazaSolutie(int n) {
    int i;

    for (i = 1; i <= n; i++)
        solutie[i] = v[i];
}

bool valid(int k) {
    int i;

    for (i = 1; i < k; i++) 
        if ((v[k] == v[i]) || (k - i == abs(v[k] - v[i])))
            return false;

    return true;
}

int back(int n) {
    bool eSolutie, prima = true;
    int k, nrSolutii = 0;

    k = 1;
    v[k] = 0;

    while (k > 0) {
        eSolutie = 0;
        while ((v[k] < n) && (!eSolutie)) {
            v[k]++;
            eSolutie = valid(k);
        }
        if (!eSolutie)
            k--;
        else {
            if (k == n) {
                if (prima) {
                    creazaSolutie(n);
                    prima = false;
                }
                nrSolutii++;
            } else {
                k++;
                v[k] = 0;
            }
        }
    }

    return nrSolutii;
}

int main() {
    int n, k, nrSolutii, i;

    fin >> n;

    nrSolutii = back(n);
    for (i = 1; i <= n; i++)
        fout << solutie[i] << ' ';
    fout << '\n' << nrSolutii;

    fin.close();
    fout.close();

    return 0;
}