J. Polygon II
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kostka would like to build a large polygon for himself. He ordered $$$n$$$ random segments. The length of the $$$i$$$-th segment will be a random real number drawn from a uniform distribution in the range $$$\pmb{(0, 2^{a_i})}$$$. The lengths of the individual segments are independently drawn. Kostka is interested in the probability that it is possible to construct a non-degenerate $$$n$$$-sided polygon from all these segments. Help him calculate it.

It can be proven that for the constraints given below, the result can be represented as a rational number $$$\frac{\ell}{m}$$$ such that the denominator $$$m$$$ is not divisible by $$$10^9 + 7$$$. Your program for the given parameters $$$a_i$$$ should output the remainder of dividing this fraction by $$$10^9 + 7$$$, i.e., a number $$$x$$$ such that $$$m \cdot x \equiv \ell$$$ modulo $$$10^9 + 7$$$.

Note: Remember that the lengths of the segments are not drawn from the interval $$$(0, a_i)$$$, but from $$$(0, 2^{a_i})$$$.

Input

The first line of the input contains a single positive integer $$$n$$$ ($$$3 \leq n \leq 1000$$$), indicating the number of ordered segments. The second line contains a sequence of $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 50$$$), indicating the parameters used to draw the lengths of the individual segments.

Output

The output should contain a single integer - the remainder of the probability divided by $$$10^9 + 7$$$ that it is possible to construct a non-degenerate $$$n$$$-sided polygon from the random segments ordered by Kostka.

Example
Input
3
0 2 0
Output
166666668
Note

The sought probability is exactly $$$\frac16$$$.