#include <fstream>
#define VAL 15

using namespace std;

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

int N, i, sol;
int v[VAL];
int s[VAL];
bool ok[VAL];
bool dg1[VAL], dg2[VAL];

void backtr(int K)
{
    int i, j;
    if (K==N+1)
      return;
    for (i=1; i<=N; i++)
    {
        if (ok[i]==false && dg1[K+i]==false && dg2[N-K+i-1]==false)
        {
            ok[i]=true;
            dg1[K+i]=true;
            dg2[N-K+i-1]=true;
            v[K]=i;
            if (K==N)
            {
                sol++;
                if (sol==1)
                  for (j=1; j<=N; j++)
                    s[j]=v[j];
            }
            backtr(K+1);
            ok[i]=false;
            dg1[K+i]=false;
            dg2[N-K+i-1]=false;
        }
    }
}

int main()
{
    fin >> N;
    backtr(1);
    for (i=1; i<=N; i++)
      fout << s[i] << " ";
    fout << '\n';
    fout << sol << '\n';
    fin.close();
    fout.close();
    return 0;
}