E - Random LIS 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A_1, A_2, \cdots, A_N が与えられます。

同じく長さ N の整数列 X は、 各 i (1 \leq i \leq N) について独立に、 1 \leq X_i \leq A_i を満たす整数の一様分布からランダムに選ばれます。

このとき、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

出力

期待値を mod 1000000007 で出力せよ。

入力例 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