题目描述

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

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

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

题目大意

给出一个长度为 $N$ 的序列 $A$，按照下列方式随机生成一个长度为 $N$ 的序列 $X$：
$\forall i\in[1,n]$，$X_i$ 在 $[1,A_i]$ 中的整数均匀随机。
求其最长上升子序列长度的期望，对 $10^9+7$ 取模。

3
1 2 3

2

3
2 1 2

500000005

6
8 6 5 10 9 14

959563502

提示

注釈

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

制約

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

Sample Explanation 1

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

Sample Explanation 2

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