#include <fstream>

#define lmax 15

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int n,nr;

int sol[lmax];

int folc[lmax];

inline int modul(int a)
{
    return a>=0?a:-a;
}

inline void tipar()
{
    for (int i=1;i<=n;i++)
     g<<sol[i]<<" ";
}

inline void back(int k)
{
    if (k==n+1)
     {
       nr++;

       if (nr==1)
        tipar();
     }
    else
     {
         for (int i=1;i<=n;i++)
             if (folc[i]==0)
                {
                    sol[k]=i;

                    folc[i]=1;

                    bool ok=1;

                    for(int j=1;j<k;j++)
                        if (k-j==modul(sol[j]-sol[k]))
                          {
                              ok=0;
                              break;
                          }

                     if (ok)
                      back(k+1);

                    folc[i]=0;
                }
     }
}

int main()
{
    f>>n;

    back(1);

    g<<'\n'<<nr;

    f.close();
    g.close();
}