Factorial Frequencies

In an attempt to bolster her sagging palm-reading business,Madam Phoenix has decided to offer several numerological treats toher customers. She has been able to convince them that thefrequency of occurrence of the digits in the decimal representation offactorials bear witness to their futures. Unlike palm-reading, however, she can't just conjure up these frequencies, so she hasemployed you to determine these values.

Recall that the definition of n! (that is, n factorial) is just . As she expects to use either the day of the week, the day ofthe month, or the day of the year as the value of n, you mustbe able to determine the number of occurrences of each decimal digitin numbers as large as 366 factorial (366!), which has 781 digits.

Input and Output

The input data for the program is simply a list of integers forwhich the digit counts are desired. All of these input values willbe less than or equal to 366 and greater than 0, except for the lastinteger, which will be zero. Don't bother to process this zero value;just stop your program at that point. The output format isn't toocritical, but you should make your program produce results thatlook similar to those shown below.

Madam Phoenix will be forever (or longer) in your debt; she mighteven give you a trip if you do your job well!

Sample Input

381000

Sample Output

3! --   (0)    0    (1)    0    (2)    0    (3)    0    (4)    0   (5)    0    (6)    1    (7)    0    (8)    0    (9)    08! --   (0)    2    (1)    0    (2)    1    (3)    1    (4)    1   (5)    0    (6)    0    (7)    0    (8)    0    (9)    0100! --   (0)   30    (1)   15    (2)   19    (3)   10    (4)   10   (5)   14    (6)   19    (7)    7    (8)   14    (9)   20

#include <stdio.h>
#include <string.h>
int main() {
    int f[367][805] = {}, d[367][10];
    int i, j;
    memset(d, 0, sizeof(d));
    f[0][0] = 1, d[0][1] = 1;
    for(i = 1; i <= 366; i++) {
        for(j = 0; j < 800; j++) {
            f[i][j] += f[i-1][j]*i;
            f[i][j+1] += f[i][j]/10;
            f[i][j] %= 10;
        }
        j = 800;
        while(!f[i][j]) j--;
        for(; j >= 0; j--) {
            d[i][f[i][j]]++;
        }
    }
    int n;
    while(scanf("%d", &n) == 1 && n) {
        printf("%d! --\n", n);
        for(i = 0; i < 5; i++) {
            if(i)
                printf("    ");
            else
                printf("   ");
            printf("(%d)%5d", i, d[n][i]);
        }
        puts("");
        for(i = 5; i < 10; i++) {
            if(i != 5)
                printf("    ");
            else
                printf("   ");
            printf("(%d)%5d", i, d[n][i]);
        }
        puts("");
    }
    return 0;
}