#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;

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

int v[14], st[14], N, ok=1, cnt=0;

void Afisare()
{
   cnt++;
   if (ok==1) /// prima afisare
   {
     int j;
     for (j=1; j<=N; j++)
       fout << st[j] << " ";
     ok=0;
   }
}

int Modul(int x, int y)
{
    int d;
    d = x-y;
    if (d>0) return d;
    return -d;
}

inline bool Valid(int i, int top)
{
   int j;
   if (v[i]) return 0;
   for (j=1; j<top; j++)
   {
     if (Modul(i,st[j]) == Modul(top,j))
       return 0;
   }
   return 1;
}

void Back(int top)
{
  int i, j;

  if (top==N+1) Afisare();
  else
    for (i=1; i<=N; i++)
      if (Valid(i, top)==1)
    {
       st[top]=i;
       v[i]=1;
       Back(top+1);
       v[i]=0;
    }
}

int main ()
{
  fin >> N;
  Back(1);
  fout << "\n" << cnt << "\n";
  fin.close();
  fout.close();
  return 0;
}