/* Problem 5--Tied Permutations
   This was likely the hardest problem of the set.  Of course,
   considering that the input numbers never exceeds 10, one could
   compute the values by hand and use a lookup table for this program.
   But how does one compute those values?  I looked at each integer
   partition of the input.  3, for example is 3,1+2,1+1+1.  4 is
   4,1+3,2+2,1+1+2,1+1+1+1.  Each one of these partitions represents an
   amount of tying.  4 is a 4-way tie.  1+3 is a 3-way tie.  2+2 is two
   2-way ties.  1+1+1+1 is no tie at all.  Who can be involved in a tie
   is a computation of factorials and combinations. */

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

#define MAX 10

typedef int PA[MAX];

int main (int argc, char **argv);
void factinit (void);
void Cinit (void);
void AdvancePart (PA A, int n);
int EvalPart (PA A, int n);

int fact[MAX+1];
int C[MAX+1][MAX+1];

FILE *in, *out;

int main (int argc, char **argv) {

  int n, sum;
  PA A;

 in = fopen ("prob5.in","r");
 out = fopen ("prob5.out","w");
 factinit (); /* Compute factorials up to 10! */
 Cinit (); /* Compute combinations up to 10C10 */
 while (1) {
  fscanf (in,"%d",&n);
  if (n==0) break;
  memset (A,0,sizeof A);
  A[n-1] = n; /* Initialize partition to 0,0,...,n */
  sum = 0;
  while (1) {
   sum += EvalPart (A,n); /* how many orderings does this partition */
  if (A[n-1]==1) break;   /* contribute? */
   AdvancePart (A,n); /* get the next partition */
  }
  fprintf (out,"%d\n",sum);
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* factinit computes factorials up to 10! for future use */

void factinit (void) {

  int i;

 fact[0] = 1;
 for (i = 1; i <= MAX; i++)
  fact[i] = i * fact[i-1];
}

/* Cinit computes combinations up to 10C10 for future use */

void Cinit (void) {

  int i, j;

 for (i = 0; i <= MAX; i++)
  for (j = 0; j <= MAX; j++)
   if (j>i) C[i][j] = 0;
   else if (j==0 || i==j) C[i][j] = 1;
   else C[i][j] = C[i-1][j-1] + C[i-1][j];
}

/* AdvancePart advances through all the partitions, starting from
   0,...,n ending with 1,...,1.  It increments the right-most integer it
   can increment, keeping the integers in nondecreasing order. */

void AdvancePart (PA A, int n) {

  int sum = A[n-1], i;

 for (i = n-2; i >= 0; i--) { /* looking for the right-most integer */
  sum += A[i];                /* that differs from the far-right */
  if (A[n-1]-A[i] > 1) break; /* integer by more than 1 */
 }
 A[i]++; sum -= A[i]; /* we increment that integer, and set all */
 for (i++; i < n-1; i++) { /* subsequent integers equal to that one */
  A[i] = A[i-1]; /* except the last which is set to the whatever it */
  sum -= A[i]; /* needs to be set to keep the sum equal to n */
 }
 A[n-1] = sum;
}

/* EvalPart computes the number of orderings associated with that
   partition.  First it computes how many ways to place the teams within
   the specified ties.  Then, it computes how many ways the ties
   themselves can be placed in the rankings. */

int EvalPart (PA A, int n) {

  int ct=n, prod=1, f, l, fct, i, j;

 for (j=0; A[j] == 0; j++); /* Skip past the zeros */
 for (i=j; i < n; i++) {/* There are ct teams remaining to choose from*/
  prod *= C[ct][A[i]];/* and we want to choose A[i] of them, or */
  ct -= A[i]; /* (ct)C(A[i]).  These are multiplied together. */
 }
 fct = fact[n-j];/*The ties can be ordered in m! ways where m is the */
 for (f=j; f < n; f=l) {/* size of the partition */
  for (l=f+1; l<n && A[f]==A[l]; l++);/* But we have to factor out */
  fct /= fact[l-f];/* repeats in the partition list by dividing by */
 } /* the factorial of the count of each repeated number */
 return prod*fct; /* we multiply the team placements by the tie */
} /* placements to get the answer. */