#include <fstream>
#include <cstdlib>

using namespace std;

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

int k=1,v[20],i,n,cont=0;
bool caut;

bool ok(int k)
{
     for (i=k-1; i>=1; --i)
     if (v[k]==v[i] || abs(i-k)==abs(v[i]-v[k]))
     return 0;
     return 1;
}

int main()
{
    f>>n;

    v[1]=0;
    while (k)
    {
         caut=0;
         while (!caut && v[k]<n)
         {
              v[k]++;
              if (ok(k)) caut=1;
          }
          if (caut==0) k--;
          else
          if (k==n)
          {
               if (cont==0)
               {
               for (i=1; i<=k; ++i) g<<v[i]<<" ";
               g<<'\n';
               }
               cont++;
          }
          else
          k++, v[k]=0;
    }
    g<<cont;
    return 0;
}