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

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

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

FILE *outf;

void main() {
  outf=fopen("ratsdiv.out","w");
  printf("Input Base <= 10000\n");
  scanf("%d",&base);
  printf("Input Upper Bound for Length of Numbers\n");
  scanf("%d",&u);
  for(len=1;len<=u;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);
  fprintf(outf,"%d   ",n); 
  num=a[n];
  printf("%d_",num);
  fprintf(outf,"%d_",num);
  c=1;
  for(i=n-1;i>=1;i--)
    if(a[i]==num) c++;
    else {
      printf("%d %d_",c,a[i]);
      fprintf(outf,"%d %d_",c,a[i]);
      num=a[i];
      c=1;
    }
  printf("%d",c);
  fprintf(outf,"%d",c); 
}

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(" ---> ");
  fprintf(outf," ---> ");
  c=0;
  do {
    reverse();
    add();
    sort();
    c++;
  } while (c<=1000);
  write();
  printf("\n");
  fprintf(outf,"\n");
  return;
}