In honor of this contest being the UTPC x WiCS contest, and with International Girls Day on November 14th, the other UTPC officers decide to give Victoria a break from problem writing for the week. Victoria decides to use this break to string bracelets for the other officers.
She has a pile of beads in $$$k$$$ different colors, with $$$c_i$$$ beads of color $$$i$$$. A bracelet is made by stringing all of her beads in a row and fastening a clasp to each end. Because the clasps are different, a bracelet is read strictly from left to right, so she never rotates or flips it. Beads of the same color are identical, so two bracelets look the same only if they have the same color at every position.
Victoria wants to know how many different bracelets she could possibly string using all of her beads. Since this number can be enormous, help her compute it modulo $$$10^9 + 7$$$.
The first line contains a single integer $$$k$$$ ($$$1 \le k \le 2 \cdot 10^5$$$), the number of bead colors.
The second line contains $$$k$$$ integers $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \le c_i$$$), where $$$c_i$$$ is the number of beads of color $$$i$$$. It is guaranteed that the total number of beads satisfies $$$\sum_{i=1}^{k} c_i \le 2 \cdot 10^5$$$.
Print a single integer, the number of distinct bracelets Victoria can string using all of her beads, modulo $$$10^9 + 7$$$.
21 1
2
31 2 1
12
15
1
In the first example, color $$$1$$$ is red and color $$$2$$$ is blue. Victoria has one bead of each color, so she can string them as $$$(1, 2)$$$ (red, blue) or $$$(2, 1)$$$ (blue, red), for $$$2$$$ bracelets.
In the second example, she has beads of colors forming the multiset $$$\{1, 2, 2, 3\}$$$. The 12 distinct bracelets are $$$(1, 2, 2, 3)$$$, $$$(1, 2, 3, 2)$$$, $$$(1, 3, 2, 2)$$$, $$$(2, 1, 2, 3)$$$, $$$(2, 1, 3, 2)$$$, $$$(2, 2, 1, 3)$$$, $$$(2, 2, 3, 1)$$$, $$$(2, 3, 1, 2)$$$, $$$(2, 3, 2, 1)$$$, $$$(3, 1, 2, 2)$$$, $$$(3, 2, 1, 2)$$$, and $$$(3, 2, 2, 1)$$$.
In the third example, every bead is the same color, so there is only one possible bracelet no matter how she strings them.