配点 : $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$ で出力せよ。

3
1 2 3

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}$ です。

3
2 1 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$ を出力してください。

6
8 6 5 10 9 14

959563502