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

ifstream f ("damesah.in");
ofstream g ("damesah.out");

const int NMAX = 13;
int x[NMAX+1], n, nrsol;

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

void afis() {
    for (int i=1; i<=n; i++)
        g << x[i] << ' ';
    g << '\n';
}

void backTracking(int k) {
    if (k <= n) {
        for (x[k]=1; x[k] <= n; x[k]++)
            if (valid(k))
                backTracking(k+1);
    } else {
        nrsol++;
        if (nrsol == 1)
            afis();
    }
}

int main()
{
    f >> n;
    backTracking(1);
    g << nrsol;
    return 0;
}