Factorial Frequencies

Time limit1sMemory limit128 MB

Summary

Read n values until a terminating 0, and for each n count how many times each digit 0 through 9 appears in the decimal representation of n! (n up to 366), printing the counts in a fixed two-line format.

Level: Easy3 of 10
Topics: Math, Implementation, Simulation
Solved: No attempts yet

Problem

To boost her struggling palm-reading business, Madam Phoenix has decided to offer her customers a few numerology novelties. She has convinced them that the frequency with which each digit appears in the decimal representation of a factorial reveals something about their future. Unlike palm-reading, though, she cannot simply invent these frequencies, so she has hired you to compute them.

Recall that $n!$ (that is, $n$ factorial) is defined as $1 \times 2 \times 3 \times \cdots \times n$ . Because she plans to use the day of the week, the day of the month, or the day of the year as the value of $n$ , your program must be able to count how many times each decimal digit occurs in numbers as large as $366!$ , which has $781$ digits.

Input

The input is a list of integers, one per line, for which the digit counts are wanted. Every input value is greater than $0$ and less than or equal to $366$ , except for the last value, which is $0$ . Do not process this final $0$ ; stop reading at that point.

Output

For each input value $n$ (processed in order), print a line of the form n! --. Then print the count of each decimal digit in $n!$ across two lines: digits $0$ through $4$ on the first line and digits $5$ through $9$ on the second.

Each digit entry is printed as three spaces, the digit in parentheses, the count right-justified in a field five characters wide, and a single trailing space — that is, the C-style format (%d)%5d repeated for the five digits on the line. Both lines therefore end with a trailing space. Follow this output format exactly.

Hint

Madam Phoenix will be forever (or longer) in your debt; she might even send you on a trip if you do the job well!

Examples4

Example 1

Input

Expected output

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

Example 2

Input

1
0

Expected output

1! --
   (0)    0    (1)    1    (2)    0    (3)    0    (4)    0 
   (5)    0    (6)    0    (7)    0    (8)    0    (9)    0

Example 3

Input

5
0

Expected output

5! --
   (0)    1    (1)    1    (2)    1    (3)    0    (4)    0 
   (5)    0    (6)    0    (7)    0    (8)    0    (9)    0

Example 4

Input

2
0

Expected output

2! --
   (0)    0    (1)    0    (2)    1    (3)    0    (4)    0 
   (5)    0    (6)    0    (7)    0    (8)    0    (9)    0