Problem Statement

Petals have been made in order to artificially create a large, beautiful flower.
All petals have the same shape, but differ in color.
There are $K$ colors, numbered from $1$ to $K$, and there are $C_i$ petals of color $i$.
A flower is made by arranging all of these petals in a circle.
Write a program that finds the number of different flowers that can be made.
Here, arrangements that coincide by rotation are considered the same flower.
Even if two arrangements coincide when flipped upside down, they are considered different flowers unless they coincide by rotation.
Since the answer can be large, output the remainder when divided by $10^9+7$.

Input

$K$
$C_1$ $C_2$ $\cdots$ $C_K$

$1 \leq K \leq 10^5$
$C_1 + C_2 + \cdots + C_K \leq 10^6$
$C_k \geq 1$

Output

Output the number of flower patterns that can be made, ${\rm mod}\ 10^9+7$, on $1$ line.
Print a newline at the end.

Sample

2
2 2

2

2
9 1

1

3
8 1 1

9

3
3 3 3

188