#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
   int n;
   int nexpr;
   char **expr;
   char *etype;
} EXPR;

void combineexpr ( char *str, char *e1, char *e2, char e1type, char e2type, char op )
{
   if (op == '+') sprintf(str, "%s+%s", e1, e2);
   else {
      if ((e1type == '+') && (e2type == '+')) sprintf(str, "(%s)*(%s)", e1, e2);
      else if (e1type == '+') sprintf(str, "(%s)*%s", e1, e2);
      else if (e2type == '+') sprintf(str, "%s*(%s)", e1, e2);
      else sprintf(str, "%s*%s", e1, e2);
   }
}

EXPR findallexpr ( int n )
{
   EXPR E, *F;
   int i, j, k, l, s, u, v, w;
   char *str;

   str = (char *)malloc(4 * n * sizeof(char));

   F = (EXPR *)malloc((n+1) * sizeof(EXPR));

   F[0].n = 0;
   F[0].nexpr = 0;
   F[0].expr = NULL;
   F[0].etype = NULL;

   F[1].n = 1;
   F[1].nexpr = 1;
   F[1].expr = (char **)malloc(sizeof(char *));
   F[1].expr[0] = (char *)malloc(2 * sizeof(char));
   strcpy(F[1].expr[0], "1");
   F[1].etype = (char *)malloc(sizeof(char));
   F[1].etype[0] = '+';

   for (i=2; i<=n; ++i) {
      l = 0;
      for (j=1; j<=i/2; ++j) {
         k = i - j;
         l += F[j].nexpr * F[k].nexpr;
      }
      s = (int)sqrt(i);
      for (j=2; j<=s; ++j) {
         if (i % j == 0) {
            k = i / j;
            l += F[j].nexpr * F[k].nexpr;
         }
      }
      F[i].n = i;
      F[i].nexpr = l;
      F[i].expr = (char **)malloc(l * sizeof(char *));
      F[i].etype = (char *)malloc(l * sizeof(char));

      l = 0;
      for (j=1; j<=i/2; ++j) {
         k = i - j;
         for (u=0; u<F[j].nexpr; ++u) {
            for (v=0; v<F[k].nexpr; ++v) {
               combineexpr(str, F[j].expr[u], F[k].expr[v], F[j].etype[u], F[k].etype[v], '+');
               for (w=0; w<l; ++w) if (!strcmp(str,F[i].expr[w])) break;
               if (w == l) {
                  F[i].expr[l] = (char *)malloc((1 + strlen(str)) * sizeof(char));
                  strcpy(F[i].expr[l], str);
                  F[i].etype[l] = '+';
                  ++l;
               }
            }
         }
      }
      for (j=2; j<=s; ++j) {
         if (i % j == 0) {
            k = i / j;
            for (u=0; u<F[j].nexpr; ++u) {
               for (v=0; v<F[k].nexpr; ++v) {
                  combineexpr(str, F[j].expr[u], F[k].expr[v], F[j].etype[u], F[k].etype[v], '*');
                  for (w=0; w<l; ++w) if (!strcmp(str,F[i].expr[w])) break;
                  if (w == l) {
                     F[i].expr[l] = (char *)malloc((1 + strlen(str)) * sizeof(char));
                     strcpy(F[i].expr[l], str);
                     F[i].etype[l] = '*';
                     ++l;
                  }
               }
            }
         }
      }
      F[i].nexpr = l;
      F[i].expr = (char **)realloc(F[i].expr, l * sizeof(char *));
      F[i].etype = (char *)realloc(F[i].etype, l * sizeof(char));
   }
   E.n = n;
   E.nexpr = F[n].nexpr;
   E.expr = (char **)malloc(E.nexpr * sizeof(char *));
   E.etype = (char *)malloc(E.nexpr * sizeof(char));
   for (l=0; l<E.nexpr; ++l) {
      E.expr[l] = (char *)malloc((1 + strlen(F[n].expr[l])) * sizeof(char));
      strcpy(E.expr[l], F[n].expr[l]);
      E.etype[l] = F[n].etype[l];
   }
   for (i=1; i<=n; ++i) {
      for (l=0; l<F[i].nexpr; ++l) free(F[i].expr[l]);
      free(F[i].expr);
      free(F[i].etype);
   }
   free(str);
   return E;
}

int count1 ( char *str )
{
   char *t;
   int cnt;

   t = str; cnt = 0;
   while (1) {
      t = strchr(t, '1');
      if (t == NULL) break;
      ++cnt;
      ++t;
   }
   return cnt;
}

void sortexpr ( EXPR E )
{
   int m, i, j, k;
   char *t, c;
   int *N1;

   m = E.nexpr;
   N1 = (int *)malloc(m * sizeof(int));
   for (i=0; i<m; ++i) N1[i] = count1(E.expr[i]);
   for (j=m-2; j>=0; --j) {
      for (i=0; i<=j; ++i) {
         if (N1[i] > N1[i+1]) continue;
         if ((N1[i] == N1[i+1]) && (strlen(E.expr[i]) >= strlen(E.expr[i+1]))) continue;
         k = N1[i]; N1[i] = N1[i+1]; N1[i+1] = k;
         t = E.expr[i]; E.expr[i] = E.expr[i+1]; E.expr[i+1] = t;
         c = E.etype[i]; E.etype[i] = E.etype[i+1]; E.etype[i+1] = c;
      }
   }
}

void printallexpr ( EXPR E )
{
   int l;

   printf("%-3d", E.n);
   for (l=0; l<E.nexpr; ++l) {
      printf("%s = %s\n", (l) ? "   " : "", E.expr[l]);
   }
   printf("... %d expressions\n", E.nexpr);
}

int main ( int argc, char *argv[] )
{
   int n;
   EXPR E;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n = %d\n", n);

   E = findallexpr(n);
   printf("\n+++ Before sorting\n");
   printallexpr(E);

   sortexpr(E);
   printf("\n+++ After sorting\n");
   printallexpr(E);

   exit(0);
}