#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
 int n,sol[15],use[15],nr,use1[15],use2[15],usec[15];

  void Back(int k)
  { int i;
     if (k>n) {nr++; if (nr==1) {for(i=1;i<=n;i++) g<<sol[i]<<" "; g<<"\n";} }
      else
       {
         for(i=1;i<=n;i++)
          {
              if (!usec[i] && !use[k+i] && ((k>=i && !use1[k-i]) || (k<i && !use2[i-k]) ))
               {
                  usec[i]=1;
                  use[k+i]=1;
                  if (k>=i) use1[k-i]=1; else use2[i-k]=1;

                  sol[k]=i; Back(k+1);

                  usec[i]=0;
                  use[k+i]=0;
                  if (k>=i) use1[k-i]=0; else use2[i-k]=0;
               }
          }
       }

  }

int main()
{ f>>n;
   Back(1);
   g<<nr;
    return 0;
}