#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int n, x[20];
long long nrsol = 0;
bool gasit = false;
int prima[20];

bool valid(int k) {
    for (int i = 1; i < k; i++)
        if (x[k] == x[i] || abs(k - i) == abs(x[k] - x[i]))
            return false;
    return true;
}

void backt(int k) {
    for (int v = 1; v <= n; v++) {
        x[k] = v;
        if (valid(k)) {
            if (k == n) {
                nrsol++;
                if (!gasit) {
                    gasit = true;
                    for (int i = 1; i <= n; i++)
                        prima[i] = x[i];
                }
            } else
                backt(k + 1);
        }
    }
}

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

    fin >> n;
    backt(1);
    for (int i = 1; i <= n; i++)
        {
        fout << prima[i];
        if (i < n)
            fout << ' ';
        else
            fout << '\n';
    }
    fout << nrsol << '\n';

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