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