/* Tutorial on Reverse Search */
/* Section 5: An Improved Implementation for Permutations */

#include <stdio.h>
#define TRUE 1
#define FALSE 0

typedef int perm[100];

int n;				/* global variable for size of permutation */

findindex(perm v)  /* find first out of order position in v */
{
  int i;
  for(i=1; i < n && v[i] < v[i+1]; i++);
  v[0]=i;
}

void output (perm v)
{
  int i;
  for (i = 1; i <= n; i++)
    printf (" %d", v[i]);
  printf ("\n");
}

void copy (perm w, perm v)
{
  int i;

  for (i = 1; i <= n; i++)
    w[i] = v[i];
}

int equal (perm w, perm v)
{
  int i;
  for (i = 1; i <= n; i++)
    if (w[i] != v[i])
      return FALSE;
  return TRUE;
}

int root (perm v)
{
  int i;
  for (i = 1; i <= n; i++)
    if (v[i] != i)
      return FALSE;
  return TRUE;
}

void swap (perm v, int j)
{
  int t;
  t = v[j];
  v[j] = v[j + 1];
  v[j + 1] = t;
}

void Adj (perm v, int j)	/* adjacency oracle */
{
  swap (v, j);
}

int f (perm v)			/* local search function */
{
  int i=1;
  while ( i < n && v[i] <= v[i + 1] ) i++;
  if (i < n)
    swap (v, i);
  return i;
}

int reverse (perm v, int j)
{
  perm w;
  int s=v[0];    /*smallest index s.t.v[s]>v[s+1]*/
  if ( j <= s-1 ) return TRUE;
  if ( j == s+1 && s <= n-2 && v[s] < v[s+2] ) return TRUE;
  return FALSE;
}

int backtrack (perm v)
{
  return f(v);
}

int reversesearch (perm v, int maxdeg)
{
  int j=0, count=1;
  output (v);
  while ( j <= maxdeg )
    {
      findindex(v);
      do j++;
          while (j <= maxdeg && !reverse (v, j));
      if (j <= maxdeg)
        {
          Adj (v, j);
          output (v); count++;
          j = 0;
        }
      else if (!root(v))
           j = backtrack (v);
    }
  return count;
}


int main ()				/* simple reverse search for permutations */
{
  int v[100];
  int i, count;

  scanf ("%d", &n);

  for (i = 1; i <= n; i++)
    v[i] = i;

  count = reversesearch (v, n - 1);
  printf ("\nnumber of permutations=%d\n", count);
  return 0;
}