Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. 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 color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen. 

Input

The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain ci, the number of balls of the i-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, modulo 1 000 000 007. 

Examples

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: 
    
    
      
    1 2 1 2 3  
    1 1 2 2 3  
    2 1 1 2 3  
    
25
35
43
38
33
47
44
40
36
41
42
33
30
49
42
62
39
40
35
43
31
42
46
42
34
33
 47
20
21
16
18
24
20
25
13
20
22
26
24
17
18
21
22
21
23
17
15
24
19
18
21
20
19
26
25
20
17
17
17
26
32
20
21
25
28
24
21
21
17
28
20
20
31
19
 3
343
317
337
 1
5
 10
100
100
100
100
100
100
100
100
100
100
 1
1
 13
67
75
76
80
69
86
75
86
81
84
73
72
76
 5
10
10
10
10
10
 11
291
381
126
39
19
20
3
1
20
45
2

362689152
 295545118
 691446102
 1
 12520708
 1
 232242896
 425711769
 902382672

#!/usr/bin/env python
# 554C_colored.py - Codeforces.com 554C Colored quiz
#
# Copyright (C) 2015 Sergey
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#       http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
Input

The first line of input will have one integer k (1<=k<=1000) the number
of colors.

Then, k lines will follow. The i-th line will contain ci, the number of
balls of the i-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, modulo 1_000_000_007.

"""

# Standard libraries
import unittest
import sys
import re

# Additional libraries


###############################################################################
# Colored Class
###############################################################################


class Colored:
    """ Colored representation """

    MOD = 1000000007

    def __init__(self, args):
        """ Default constructor """

        self.list = args

    def fact(self, n):
        result = 1
        for i in range(n):
            result *= i + 1
        return result

    def binom(self, n, k):
        return (self.fact(n) // (self.fact(n - k) * self.fact(k)))

    def f(self, i):
        if i == 0:
            return 1
        bin = self.binom(sum(self.list[:i+1]) - 1, self.list[i] - 1)

        return (bin % self.MOD) * self.f(i - 1)

    def calculate(self):
        """ Main calcualtion function of the class """
        result = self.f(len(self.list) - 1) % self.MOD

        return str(result)


###############################################################################
# Executable code
###############################################################################


def get_inputs(test_inputs=None):

    it = iter(test_inputs.split("\n")) if test_inputs else None

    def uinput():
        """ Unit-testable input function wrapper """
        if it:
            return next(it)
        else:
            return input()

    # Getting string inputs
    num = int(uinput())
    nums = [int(uinput()) for i in range(num)]

    # Decoding inputs
    inputs = nums

    return inputs


def calculate(test_inputs=None):
    """ Base class calculate method wrapper """
    return Colored(get_inputs(test_inputs)).calculate()


###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_sample_tests(self):
        """ Quiz sample tests. Add \n to separate lines """
        self.assertEqual(calculate("3\n2\n2\n1"), "3")
        self.assertEqual(calculate("4\n1\n2\n3\n4"), "1680")
        self.assertEqual(calculate(
            "10\n100\n100\n100\n100\n100\n100\n100" +
            "\n100\n100\n100"), "12520708")
        s = "1000"
        for n in range(1000):
            s += "\n1"
        self.assertEqual(calculate(s), "1")

    def test_get_inputs(self):
        """ Input string decoding testing """
        self.assertEqual(get_inputs("2\n1\n3"), [1, 3])

    def test_Colored_class__basic_functions(self):
        """ Colored class basic functions testing """

        # Constructor test
        d = Colored([2, 1])
        self.assertEqual(d.list, [2, 1])

        # Factorial using modulo
        self.assertEqual(d.fact(4), 24)

        # Binominal
        self.assertEqual(d.binom(2, 1), 2)

        # Dynamic programming function, solution for i colors
        self.assertEqual(d.f(0), 1)
        self.assertEqual(d.f(1), 1)


if __name__ == "__main__":

    # Avoid recursion limitaions
    sys.setrecursionlimit(10000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    print(calculate())
