1220 - Coins

Time Limit: 2s Memory Limit: 32MB

Submissions: 65 Solved: 17
Description
This is a problem about coins. As is known to all members in HUST ACMICPC Team, Hudedi loves money better than any other things in his life (for example: girlfriend). Every morning, his favorite thing is showing his coins to others. One morning, Mr. Yin came in when he was showing the coins and asked him a question: “How many different ways can you put all your coins in a line?”
Input
The first line of the input contains an integer T (0<T<10000). T refers to the number of the test cases followed. For each test case, the first line contains only one Integer N (1<=N<=80), which means hudedi has N different kinds of coins. The second line contains N Integers and the i-th number is named Ai (1<=Ai<=500). Ai means hudedi has Ai coins of the i-th kind.
Output
For each test case, output “Case X: ” followed by one Integer W. X means the number of the case and W means the number of ways, if W is no less than 40009, output it, or divide it by 40009 and output the remainder.
Sample Input
2
3
1 1 1
3
1 1 2
Sample Output
Case 1: 6
Case 2: 12
Hint
Source
Sempr, HUST Programming Contest 2007