#include <stdio.h>
#include <math.h>
#define SIZE 10000
#define BASE 4 

typedef enum boolean { FALSE, TRUE } Boolean;
void initial(int);
void write();
void sort();
void reverse();
void add();
int test();
void gensub(int, int, int);
void putnumck();

int a[SIZE+1], b[SIZE+1];
int d[BASE+1], p[BASE+1], x[BASE+1];
int i,n;
int len,no;

FILE *outf;

void main() {
  outf=fopen("ratsconj4.out","w");
  printf("Input length of number\n");
  scanf("%d",&len);
  no=len+BASE-2;
  for(i=1; i<=no; i++) gensub(i,1,BASE-2); 
  close(outf);
}

void initial(int m) {
  int i,j,k;
  for(i=1;i<=SIZE;i++) a[i]=0;
  k=0;
  for(i=1; i<=m; i++) {
    for(j=1; j<=p[i]; j++) b[k+j]=d[i];
    k=k+p[i];
  }
  m=k;
  for(i=1; i<=m; i++) a[i]=b[m+1-i];
  n=m;
} 
    
void sort() {
  int i,j;
  int num[BASE+1];
  for(i=0;i<=BASE-1;i++)  num[i]=0;
  for(i=1;i<=n;i++)  num[a[i]]=num[a[i]]+1;
  j=1;
  for(i=BASE-1;i>=0;i--) {
    while (num[i]>0) { 
      a[j]=i;   num[i]=num[i]-1;  j=j+1;
    }
  }
  while (a[n]==0)  n=n-1;
}

void reverse() {
  int i;
  for(i=1;i<=SIZE; i++)  b[i]=0;
  for(i=1;i<=n;i++)  b[i]=a[n+1-i];
}

void add() {
  int c,i,t;
  c=0;
  for(i=1;i<=n+1;i++) {
    t=a[i]+b[i]+c;
    a[i]=t % BASE;
    c=t/BASE;
  }
  if(a[n+1]!=0) n++;
}

void write() {
  int i,c,num;
  printf("%d   ",n);
  num=a[n];
  printf("%d_",num);
  c=1;
  for(i=n-1;i>=1;i--)
    if(a[i]==num) c++;
    else {
      printf("%d %d_",c,a[i]);
      num=a[i];
      c=1;
    }
  printf("%d",c); 
}

int test() {
  int st,i;
  st=a[1];
  for(i=1; i<=n; i++) {
    if((a[i]!=1) && (st==1)) st=0; 
    if((a[i]!=2) && (st==2)) st=0;
  }
  return st;
}

void gensub(int b, int subsc, int k) {
  int i;
  if((no-b+1)<k) return;
  if((k==1) && (b<=no)) {
    x[subsc]=b;    
    putnumck(); 
    return;
  }
  x[subsc] = b;
  for(i=b+1; i<=no; i++)  gensub(i,subsc+1,k-1);
  return;
}

void putnumck() {
  int i,m,c;
  x[0]=0;
  x[BASE-1]=no+1;
  m=0;
  for(i=1; i<=BASE-1; i++) 
    if((x[i]-x[i-1]-1)>0) { 
      m++;
      d[m] = i;
      p[m]=x[i]-x[i-1]-1;
    }
  initial(m);
  write();
  printf(" ---> ");
  c=0;
  do {
    reverse();
    add();
    sort();
    c++;
  } while (c<=100);
  if(test()!=0) { 
    write();
    printf("\n");
  } 
  else printf("\n");
  return;
}