Contest Duration: - (local time) (120 minutes) Back to Home
E - Random LIS /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

このとき、X の最長増加部分列の長さの期待値を mod 1000000007 で計算してください。

より正確には、期待値が有理数、つまりある既約分数 \frac{P}{Q} で表せること、更に R \times Q \equiv P \pmod {1000000007}, 0 \leq R < 1000000007 を満たす整数 R が一意に定まることがこの問題の制約より証明できますので、この R を出力してください。

### 注釈

X の部分列とは X の要素をいくつか抜き出して元の順に並べてできる列のことを指し、また、列 X の最長増加部分列とは、X の狭義単調増加な部分列の中で列の長さが最大のものを指します。

### 制約

• 1 \leq N \leq 6
• 1 \leq A_i \leq 10^9
• 入力は全て整数である

### 入力

N
A_1 A_2 \cdots A_N


### 入力例 1

3
1 2 3


### 出力例 1

2


X はそれぞれ確率 1/6 で次のいずれかになります。

• X = (1,1,1) のとき、最長増加部分列の長さは 1 です。
• X = (1,1,2) のとき、最長増加部分列の長さは 2 です。
• X = (1,1,3) のとき、最長増加部分列の長さは 2 です。
• X = (1,2,1) のとき、最長増加部分列の長さは 2 です。
• X = (1,2,2) のとき、最長増加部分列の長さは 2 です。
• X = (1,2,3) のとき、最長増加部分列の長さは 3 です。

よって、最長増加部分列の長さの期待値は (1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007} です。

### 入力例 2

3
2 1 2


### 出力例 2

500000005


X はそれぞれ確率 1/4 で次のいずれかになります。

• X = (1,1,1) のとき、最長増加部分列の長さは 1 です。
• X = (1,1,2) のとき、最長増加部分列の長さは 2 です。
• X = (2,1,1) のとき、最長増加部分列の長さは 1 です。
• X = (2,1,2) のとき、最長増加部分列の長さは 2 です。

よって、最長増加部分列の長さの期待値は (1 + 2 + 1 + 2) / 4 = 3 / 2 ですが、2 \times 500000005 \equiv 3 \pmod {1000000007} であるので、500000005 を出力してください。

### 入力例 3

6
8 6 5 10 9 14


### 出力例 3

959563502


Score : 700 points

### 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.

### Notes

A subsequence of a sequence X is a sequence obtained by extracting some of the elements of X and arrange them without changing the order. The longest increasing subsequence of a sequence X is the sequence of the greatest length among the strictly increasing subsequences of X.

### Constraints

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

### 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.

### 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