#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 ((k - p == abs(v[k] - v[p])) || 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;
    BKT(1);
    fout<<'\n'<<nrSol;
    return 0;
}