#include <iostream>
#include <fstream>

#define maxN 14

using namespace std;

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

int n, v[maxN], nrSol;

inline int abs(int x)
{
    if (x<0) return x;
}

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

void BKT(int k)
{
    int i,j;
    bool ok;
    if (k==n) afisare();
    else {
        for (j=0; j<n; ++j)
        {
            ok=1;
            for (i=0; i<k; ++i)
                if (v[i]==j || abs(v[i]-1)==(k-i)) ok=0;
            if (ok)
            {
                v[k]=j;
                BKT(k+1);
            }
        }
    }
}

int main()
{
    fin>>n;
    BKT(0);
    fout<<'\n'<<nrSol;
    return 0;
}