STONE2 - A Famous Stone Collector

no tags 

Mr. B loves to play with colorful stones. There are n colors of stones in his collection. Two stones with the same color are indistinguishable. Mr. B would like to select some stones and arrange them in line to form a beautiful pattern. After several arrangements he finds that it's very hard for him to enumerate all the patterns. So he asks you to write a program to count the number of different patterns.

Two patterns are considered different, if and only if they have different number of stones or have different colors on at least one position.

Input

Each test case starts with a line containing an integer n indicating the kinds of stones Mr. B have. Following this is a line containing n integers - the number of available stones of each color respectively. All the input numbers will be nonnegative and no more than 100.

Output

For each test case, display a single line containing the case number and the number of different patterns Mr. B can make with these stones, modulo 1,000,000,007, which is a prime number.

Example

Input:
3
1 1 1
2
1 2

Output:
Case 1: 15
Case 2: 8

Explanation

In the first case, suppose the colors of the stones Mr. B has are B, G and M, the different patterns Mr. B can form are: B; G; M; BG; BM; GM; GB; MB; MG; BGM; BMG; GBM; GMB; MBG; MGB.


hide comments
shuvojit: 2016-08-03 06:01:23

Note the Case statements in output format. Frustrating and useless.

Shakil Ahmed: 2013-03-17 06:39:30

why the time limit is 99s ???

Last edit: 2013-03-17 07:25:16
Rocker3011: 2012-07-31 03:13:20

i demmand that every single solution from the user Marcos Mistretta gets disqualify, cause he is cleary cheating thank you :)

Francky: 2012-06-12 16:58:50

[b]All[/b] input numbers (N and others) are less than or equal to 100. It's that I said, no ?

mehmetin: 2012-06-12 09:57:03

Last edit: 2016-03-10 18:08:17
Francky: 2012-06-11 17:03:05

@Mehmet Inal : in description, it is said, "All the input numbers will be nonnegative and no more than 100." So, you can assume n<=100.

mehmetin: 2012-06-10 13:54:27

what is the maximum for n?

Francky: 2012-06-09 16:52:21

Edit : silly mistake... got AC. Very nice problem.

Last edit: 2012-06-09 18:00:30

Added by:Fudan University Problem Setters
Date:2012-05-25
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Classical Problem, used in FDU Local Contest 2012