1220  Coins
Time Limit : 2 Second
Memory Limit : 32 MB
Submission: 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 ith number is named Ai (1<=Ai<=500). Ai means hudedi has Ai coins of the ith 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