#include<fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,v[10][10],sol=0;
int b = 1;
void wrt(int c)
{
    if(c)
    {
    for(int i = 1 ; i<=n ; i++)
        for(int j = 1; j<=n ; j++)
            if(v[j][i]==1) out<<j<<" ";
    }

    sol++;
}

int valid(int k,int m)
{

    int sus=k+1,jos=k-1;
    for(int i = m-1 ; i>0 ; i--)
    {
        if(v[sus][i]==1) return 0;
        if(v[jos][i]==1) return 0;
        if(v[k][i]==1) return 0;
        if((sus == n)||(sus==k)) sus = k; else sus++;
        if((jos == 1)||(jos == k)) jos=k ; else jos--;
    }
    return 1;

}

void back(int m)
{
    if(m==n+1) {wrt(b);b=0;}
      else
      {

          int k = 0;
          while(k<n)
          {
            k++;
            v[k-1][m]=0;
            v[k][m]=1;
            if(valid(k,m)) back(m+1);
            if(k==n) v[k][m]=0;
          }
      }
}

int main()
{
   in>>n;
    back(1);
    out<<"\n"<<sol;
    in.close();
    out.close();
    return 0;
}