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

#define maxN 14

using namespace std;

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

bool gata;
int n, v[maxN],nrSol;
const int nr_solutii[]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184};

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]<<" ";
    gata=true;
}

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

int main()
{
    fin>>n;
    BKT(1);
    fout<<'\n'<<nr_solutii[n];
    return 0;
}