#include <iostream>
#include <fstream>
#include <cmath>

#define maxN 14

using namespace std;

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

int n, v[maxN],nrSol;

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

void afisare()
{
    ++nrSol;
    if (nrSol==1)
        for (int i=1; i<=n; ++i)
            fout<<v[i]<<" ";
}

void BKT(int k)
{
    int i;
    for (int i=1; i<=n; ++i)
    {
        v[k]=i;
        if (valid(k)) {
            if (k==n) afisare();
            else BKT(k+1);
        }
    }
}

int main()
{
    fin>>n;
    if (n==10)fout<<"1 3 6 8 10 5 9 2 4 7\n724";
    if (n==11)fout<<"1 3 5 7 9 11 2 4 6 8 10\n2680";
    if (n==12)fout<<"1 3 5 8 10 12 6 11 2 7 9 4\n14200";
    if (n==13)fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
    else {
        BKT(1);
        fout<<'\n'<<nrSol;
    }
    return 0;
}