#include <fstream>

#define lmax 15

using namespace std;

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

int n,nr;

int sol[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 bool valid(int k)
{
    for(int i=1;i<k;i++)
      if (k-i==modul(sol[i]-sol[k]) || sol[i]==sol[k])
       return 0;

    return 1;
}

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

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

                    if (valid(k))
                      back(k+1);

            }
     }
}

int main()
{
    f>>n;

    back(1);

    g<<'\n'<<nr;

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