Problem Statement

Given is an integer sequence of length N: $A_1, A_2, \cdots, A_N$.
An integer sequence X, which is also of length N, will be chosen randomly by independently choosing X_i from a uniform distribution on the integers $1, 2, \ldots, A_i$ for each $i (1 \leq i \leq N)$.
Compute the expected value of the length of the longest increasing subsequence of this sequence X, modulo 1000000007.
More formally, under the constraints of the problem, we can prove that the expected value can be represented as a rational number, that is$, an irreducible fraction \frac{P}{Q}$, and there uniquely exists an integer R such that $R \times Q \equiv P \pmod {1000000007}$ and $0 \leq R < 1000000007$, so print this integer R.

Input

Input is given from Standard Input in the following format:
N
$A_1 A_2 \cdots A_N$

Output

Print the expected value modulo 1000000007.

Constraints

• $1 \leq N \leq 6$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Sample Input 1

3
1 2 3

Sample Output 1

2

X becomes one of the following, with probability 1/6 for each:

• X = (1,1,1), for which the length of the longest increasing subsequence is 1;
• X = (1,1,2), for which the length of the longest increasing subsequence is 2;
• X = (1,1,3), for which the length of the longest increasing subsequence is 2;
• X = (1,2,1), for which the length of the longest increasing subsequence is 2;
• X = (1,2,2), for which the length of the longest increasing subsequence is 2;
• X = (1,2,3), for which the length of the longest increasing subsequence is 3.

Thus, the expected value of the length of the longest increasing subsequence is $(1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007}$.

Sample Input 2

3
2 1 2

Sample Output 2

500000005

X becomes one of the following, with probability 1/4 for each:

• X = (1,1,1), for which the length of the longest increasing subsequence is 1;
• X = (1,1,2), for which the length of the longest increasing subsequence is 2;
• X = (2,1,1), for which the length of the longest increasing subsequence is 1;
• X = (2,1,2), for which the length of the longest increasing subsequence is 2.

Thus, the expected value of the length of the longest increasing subsequence is $(1 + 2 + 1 + 2) / 4 = 3 / 2. Since 2 \times 500000005 \equiv 3 \pmod {1000000007}$, we should print 500000005.

Sample Input 3

6
8 6 5 10 9 14

Sample Output 3

959563502

见题面 Input 部分

见题面 Output 部分