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?”
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.
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.