Kyoya Ootori has a bag withncolored balls that are colored withkdifferent
colors. The colors are labeled from1tok.
Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of coloribefore
drawing the last ball of colori?+?1for allifrom1tok?-?1.
Now he wonders how many different ways this can happen.
Input
The first line of input will have one integerk(1?≤?k?≤?1000)
the number of colors.
Then,klines will follow. Thei-th
line will containci,
the number of balls of thei-th color (1?≤?ci?≤?1000).
The total number of balls doesn‘t exceed 1000.
Output
A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo1?000?000?007.
Sample test(s)
input
3
2
2
1
output
3
input
4
1
2
3
4
output
1680
Note
In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:
