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 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.